求助一个 G 家高频题的最优解

楼主~~是最后一个词还是有overlapping 的几个词都行呀？~~

大米不够，看不了

Vidda_小毛 发表于 2019-5-3 08:53
楼主~~是最后一个词还是有overlapping 的几个词都行呀？~~

只有最后一个词

这是一道LEETCODE原题，最优解应该是构建一个带权值的graph，然后当做旅行商问题，DP求解

补充内容 (2019-5-3 10:43):
943. Find the Shortest Superstring

以词为点，字符串为边，等价于任意图的最长路问题，是NP-complete的，不存在很快的解法，brute force问题不大
可以以“已经用过哪些边+现在位于哪个点”为状态做DP，复杂度是O(N^2*2^N)，比搜索的O(N!)好一些但好得有限

http://www.mathcs.emory.edu/~che ... est-path-in-dag.pdf
纯猜，卤煮如果当初问能不能assume acyclic面试官肯定同意的否则一句话带过就不用做了
走过路过加个米 存点米用。。

请问是LC 那一道题目啊

raistlins 发表于 2019-5-3 10:41
这是一道LEETCODE原题，最优解应该是构建一个带权值的graph，然后当做旅行商问题，DP求解

补充内容 (2019- ...

我不觉得这个是Travelling Salesman Problem, 因为 TSP 要求每个点都要经过但是这个题只要求找前后词 match 的

大米不够，看不了。。。

显然TSP..
只能走到特定的点就是