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

OP 上个月面 G 的 L5 被低球了一个 L4, 主要原因是一轮算法没有写出最优解? 题是这样的:

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

地里大神们能不能分享一下对这题的看法? 谢谢

这是一道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!)好一些但好得有限

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

只有最后一个词

brute force solution 不是建所有字的组合然后一个个查长度?

general graph 求最长path？

backtrack 建所有组合是我能想到的最优解了, 因为要算最终词的长度而不是词数而且要求返回最终的词, 我就没往 DP 方向去想. 能否分享你的高见?

14417335 发表于 2019-5-3 02:17
general graph 求最长path？

不太一样, 因为这个会有 loop, "abc" "abbc", "abbbc", "cba", "cbba", "cbbba" 就不好搞

lokilokiloki 发表于 2019-5-2 13:24
不太一样, 因为这个会有 loop, "abc" "abbc", "abbbc", "cba", "cbba", "cbbba" 就不好搞

是有loop，所以我说general graph。否则是DAG啊

无环有向图的最长路径问题有线性解。关键是这图是不是有环。面试官有提到输入的限制吗？比如这样的输入是否允许："katie loves simon", "simon loves tracy", "tracy loves katie"。

补充内容 (2019-5-2 11:40):
问之前没刷新，原来不是DAG，这题考的比较奇怪，应该是NP hard。

感觉分两种情况: 1.不带环的话，其实就是n-ary tree, 然后bottom up返回最长路径，中间过程中记录路径，应该是O(n)? n是node个数。2. 环的情况单独考虑，找最大环。最后两者取最大的。

DFS没错，但要带一个memory。比如你算过了以String A为起始的最长结果，就存下来，下次算String B的时候，如果中间遇到了String A，直接加上就好了不用继续遍历。

既然题目给出的是list，那么我默认这些词是有顺序的。
如果是这样的话，那显然就是DP啊，而且就是个medium而已。