[leetcode/lintcode 题解] 谷歌面试题:最短超级串 算法 刷题解法

DanielZhao 17天前 31


给定一个字符串数组 A,找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A中另一个字符串的子字符串。

1.1 <= A.length <= 12

2.1 <= A[i].length <= 20

样例 1:

样例 2:

在线评测地址: https://www.lintcode.com/problem/find-the-shortest-superstring/?utm_source=sc-xytsq-zq

【题解】

考点:dp

题解:1.我们必须把单词放在一行中,每个单词都可能与前一个单词重叠。尽量使单词的总重叠量最大化。

2.假设我们已经把一些单词放在我们的行中,以单词A[i]结尾。现在假设我们把单词A[j]作为下一个单词,而单词A[j]还没有被放下。重叠量增加A[i]和A[j]重叠部分。

3.我们可以使用动态规划来解决。让dp(mask,i)表示放下一些单词(由mask表示放下哪些单词)后的总重叠量,其中A[i]是最后一个放下的单词。然后,关键是dp(mask ^(1<<j),j)=max(overlap(a[i],a[j])+dp(mask,i))。

4.当然,这只告诉我们每一组单词的最大重叠是什么。我们还需要记住沿途的每一个选择(即使dp(mask ^(1<<j),j)达到最小值的具体i),这样就可以重建答案。

更多语言代码参见:https://www.jiuzhang.com/solution/find-the-shortest-superstring/?utm_source=sc-xytsq-zq

最新回复 (0)
返回