美文网首页
[leetcode/lintcode 题解] 谷歌面试题:最短超

[leetcode/lintcode 题解] 谷歌面试题:最短超

作者: SunnyZhao2019 | 来源:发表于2020-06-28 19:33 被阅读0次

    给定一个字符串数组 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题解

    相关文章

      网友评论

          本文标题:[leetcode/lintcode 题解] 谷歌面试题:最短超

          本文链接:https://www.haomeiwen.com/subject/kutgfktx.html