給定一個(gè)字符串?dāng)?shù)組 A，找到以 A 中每個(gè)字符串作為子字符串的最短字符串。

我們可以假設(shè) A 中沒有字符串是 A中另一個(gè)字符串的子字符串。

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題解

【題解】

考點(diǎn)：dp

題解：1.我們必須把單詞放在一行中，每個(gè)單詞都可能與前一個(gè)單詞重疊。盡量使單詞的總重疊量最大化。

2.假設(shè)我們已經(jīng)把一些單詞放在我們的行中，以單詞A[i]結(jié)尾?，F(xiàn)在假設(shè)我們把單詞A[j]作為下一個(gè)單詞，而單詞A[j]還沒有被放下。重疊量增加A[i]和A[j]重疊部分。

3.我們可以使用動(dòng)態(tài)規(guī)劃來解決。讓dp（mask，i）表示放下一些單詞（由mask表示放下哪些單詞）后的總重疊量，其中A[i]是最后一個(gè)放下的單詞。然后，關(guān)鍵是dp（mask ^（1<<j），j）=max（overlap（a[i]，a[j]）+dp（mask，i））。

4.當(dāng)然，這只告訴我們每一組單詞的最大重疊是什么。我們還需要記住沿途的每一個(gè)選擇（即使dp（mask ^（1<<j），j）達(dá)到最小值的具體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題解