[leetcode/lintcode 题解] 谷歌面试题：最短超级串

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

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

1.1 <= A.length <= 12

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

样例 1:

输入：["alex","loves","lintcode"]
输出："alexloveslintcode"
解释："alex","loves","lintcode"的全排列可以作为答案

样例 2:

输入：["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"
解释："gctaagttcatgcatc"中包含在A中的子串是"gcta","ctaagt","ttca","catg","atgcatc"。

在线评测地址: lintcode题解

【题解】

考点：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），这样就可以重建答案。

class Solution {
    public String shortestSuperstring(String[] A) {
        int N = A.length;

        // Populate overlaps
        int[][] overlaps = new int[N][N];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) if (i != j) {
                int m = Math.min(A[i].length(), A[j].length());
                for (int k = m; k >= 0; --k)
                    if (A[i].endsWith(A[j].substring(0, k))) {
                        overlaps[i][j] = k;
                        break;
                    }
            }
        }
        // dp[mask][i] = most overlap with mask, ending with ith element
        int[][] dp = new int[1<<N][N];
        int[][] parent = new int[1<<N][N];
        for (int mask = 0; mask < (1<<N); ++mask) {
            Arrays.fill(parent[mask], -1);

            for (int bit = 0; bit < N; ++bit) {
                if (((mask >> bit) & 1) > 0) {
                // Let's try to find dp[mask][bit].  Previously, we had
                // a collection of items represented by pmask.
                    int pmask = mask ^ (1 << bit);
                    if (pmask == 0) {
                        continue;
                    }
                    for (int i = 0; i < N; ++i) if (((pmask >> i) & 1) > 0) {
                        // For each bit i in pmask, calculate the value
                        // if we ended with word i, then added word 'bit'.
                        int val = dp[pmask][i] + overlaps[i][bit];
                        if (val > dp[mask][bit]) {
                            dp[mask][bit] = val;
                            parent[mask][bit] = i;
                        }
                    }
                }
            }
        }

        // # Answer will have length sum(len(A[i]) for i) - max(dp[-1])
        // Reconstruct answer, first as a sequence 'perm' representing
        // the indices of each word from left to right.

        int[] perm = new int[N];
        boolean[] seen = new boolean[N];
        int t = 0;
        int mask = (1 << N) - 1;

        // p: the last element of perm (last word written left to right)
        int p = 0;
        for (int j = 0; j < N; ++j) {
            if (dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p]) {
                p = j;
            }
        }

        // Follow parents down backwards path that retains maximum overlap
        while (p != -1) {
            perm[t++] = p;
            seen[p] = true;
            int p2 = parent[mask][p];
            mask ^= 1 << p;
            p = p2;
        }

        // Reverse perm
        for (int i = 0; i < t/2; ++i) {
            int v = perm[i];
            perm[i] = perm[t-1-i];
            perm[t-1-i] = v;
        }

        // Fill in remaining words not yet added
        for (int i = 0; i < N; ++i) if (!seen[i])
            perm[t++] = i;

        // Reconstruct final answer given perm
        StringBuilder ans = new StringBuilder(A[perm[0]]);
        for (int i = 1; i < N; ++i) {
            int overlap = overlaps[perm[i-1]][perm[i]];
            ans.append(A[perm[i]].substring(overlap));
        }

        return ans.toString()

更多语言代码参见：leetcode/lintcode题解