lc-find-the-shortest-superstring.org

LC 943. Find the Shortest Superstring

https://leetcode.com/problems/find-the-shortest-superstring/

其实这题也是状态压缩DP和全排列之间的关系。

从全排列考虑的话，我们可以全排列所有的串，这个全排列就是覆盖的顺序，那么去掉重合的部分就是最短字符串。

因为这个问题有最优化的子结构，比如S1,S2,S3的最优覆盖f(S1,S2,S3)一定是来自

• fx(f(S1,S2), S3)
• fx(f(S1,S3), S2)
• fx(f(S2,S3), S1)

所以我们可以通过枚举所有状态来解决问题，fx(a, b)就是a+b或者是b+a的最短覆盖串（去掉重合的部分）。

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        inf = 1 << 30
        SZ = 1 << n
        dp = [(inf, '') for _ in range(SZ)]
        for i in range(n):
            dp[1 << i] = len(A[i]), A[i]

        def common(a, b):
            res = a + b
            for k in reversed(range(1, min(len(a), len(b)) + 1)):
                if a[-k:] == b[:k]:
                    res = a + b[k:]
                    break
            return res

        for st in range(SZ):
            for i in range(n):
                if st & (1 << i) or dp[st][0] == inf:
                    continue
                a = dp[st][1]
                b = A[i]

                c = common(a, b)
                d = common(b, a)
                res = c if len(c) < len(d) else d
                st2 = st | (1 << i)
                if len(res) < dp[st2][0]:
                    dp[st2] = len(res), res

        sz, ans = dp[SZ - 1]
        # print(sz)
        return ans