0943. Find the Shortest Superstring

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Constraints:

1 <= words.length <= 12
1 <= words[i].length <= 20
words[i] consists of lowercase English letters.
All the strings of words are unique.

解法1

这个是真的难. 这个标准解法是真的苟.

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length, len = 1<<n;
        
        // ovarlaps[i][j] 表示word[i] , word[j]的重叠部分长度(i在前, j在后)
        // 如果没有重叠部分,则记为0(初始值)
        int[][] overlaps = new int[n][n];
        for(int i = 0; i < n; i++){
            String s1 = words[i];
            for(int j = 0; j < n; j++){
                if(i == j)
                    continue;
                String s2 = words[j];
                int m = Math.min(s1.length(), s2.length());
                // 判断是否有重叠, 因为没有包含的情况, 所以从m-1开始计算
                for(int k = m - 1; k >=0; k--)
                    if(s1.endsWith(s2.substring(0, k))){
                        overlaps[i][j] = k;
                        break;
                    }
            }
        }
        
        // mask的二进制形式表示当前的重叠状态,最多只有20个字符串,所以int(32位)够用
        // 比如, 00010011, 表示一共8个字符串,其中有3个字符串(第4,7,8位)可以前后重叠拼接起来
        // dp[mask][j],保存拼接状态为mask(的二进制形式), 而最后的字符串为words[j]时,各个字符串之间重叠部分的总长度
        // 如果没有重叠部分,则记为0(初始值)
        int[][] dp = new int[len][n];
        // parent[mask][j],保存表示拼接状态为mask(的二进制形式), 而最后的字符串为words[j]时,j的前一个字符在words中的位置i
        int[][] parent = new int[len][n];;
        
        // 遍历mask所有可能的组合
         for(int mask = 0; mask < len; mask++){
             // 初始状态, parent中对应的前一个字符的位置为-1
             Arrays.fill(parent[mask], -1);
             
             // 计算mask的二进制形式的每一位
             for(int j = 0; j < n; j++)
                 
                 // 如果当前位为1(有用到当前字符串)
                 if(((mask >> j) & 1) > 0){
                     
                     // pmask的二进制形式,表示去掉当前位(j)之后剩下的拼接状态
                     // 比如, mask = 01001,j = 3, 计算得到 pmask = 00001
                     // 比如, mask = 01000,j = 3, 计算得到 pmask = 00000
                     int pmask = mask ^ (1 << j);
                     // 如果为0,表示已经没有剩下的字符,跳过当前j
                     if(pmask == 0)
                         continue;
                     
                     // 计算dp[mask][j]
                     // 在mask和j确定的情况下,遍历pmask,求得最大长度,并更新parent中对应的值
                     // 第一个问题, 为什么是最大值而不是最小值?????????????????????????
                     //            因为dp保存的是重叠部分的长度和, 重叠越多, 拼接后的字符串越短
                     // 第二个问题, dp[pmask][i] + overlaps[i][j], words[i]的字符可能会有双重计算的问题.
                     //            没有问题. 因为都是保存的重叠部分的长度, 就算有, 也可以通过计算消除
                     for(int i = 0; i < n; i++)
                         // 如果当前位为1(有用到当前字符串)
                         if(((pmask >> i) & 1) > 0){
                             int val = dp[pmask][i] + overlaps[i][j];
                             if(val > dp[mask][j]){
                                 dp[mask][j] = val;
                                 parent[mask][j] = i;
                             }
                         }
                 }
         }
        // 保存字符串的排列顺序
        int[] perm = new int[n];
        // 标记字符串是否被访问
        boolean[] isVisited = new boolean[n];
        int t = n - 1, mask = len - 1;
        
        // 得到当所有字符串都连起来时,有最长重叠区域的末尾字符串的位置p
        int p = 0;
        for(int j = 0; j < n; j++)
            if(dp[len - 1][j] > dp[len - 1][p])
                p = j;
        
        // 从最后一个字符串位置p,逆向得到所有字符串的位置,并存入perm中
        while(p != -1){
            perm[t--] = p;
            // 标记为已访问
            isVisited[p] = true;
            int p2 = parent[mask][p];
            // 去掉当前位置p,得到新的mask
            mask ^= 1 << p;
            p = p2;
        }
        
        // 如果有没有访问到的字符串,依次加在前面
        for(int i = 0; i < n; i++)
            if(!isVisited[i])
                perm[t--] = i;
        
        // 得到结果
        StringBuilder res = new StringBuilder(words[perm[0]]);
        for(int i = 1; i < n; i++){
            int pre = perm[i - 1], cur = perm[i];
            int overlap = overlaps[pre][cur];
            res.append(words[cur].substring(overlap));
        }
        
        return res.toString();
    }
}

0943. Find the Shortest Superstring - kumaeki/LeetCode GitHub Wiki

解法1