943. Find the Shortest Superstring

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

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

Example 2:

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

Note:

  1. 1 <= A.length <= 12
  2. 1 <= A[i].length <= 20

这道题给了一个字符串数组A,让我们找一个最短的字符串,使得所有A中的字符串是都该字符串的子串,并给了两个例子。通过第一个例子可以发现,假如任意两个字符串首尾没有重复字母的话,其就是所有字符串直接连接起来即可。但是如果有重复字母的话,比如 abc 和 bca,二者连接起来就是 abca,而不是 abcbca 了,因为 bc 两个字母是可以复用的,这是本题的难点。如果啥也不考虑,直接上最暴力的破解方法,当然就是尝试数组A中n个字符串的各种全排列方式,然后在两两之间去掉复用的字符,选长度最短的那一种,但这种无脑暴力的方法的时间复杂度是n的阶乘,就是传说中的 NP Hard,对计算机十分的不友好,计算机最多算到 n=12 左右,而这道题刚好n的范围不大于12,这难道是在引诱我们暴力平推么,这么想的话就是不尊重 OJ 了,No Way!本题最大的难点还是要求出最优解时各个字符串的排列顺序,知道了这个顺序,去除复用字符神马的都是浮云。这里如果将A中的n个字符串各自都看作一个结点,实际上要求的就是按照某个顺序依次经过所有的结点,这其实就是著名的旅行推销员问题 Travelling Salesman Problem了,注意跟哈密顿回路 Hamiltonian Cycle区分开来,哈密顿回路是问是否有能经过所有结点并回到起始结点的路径,而 TSP 是一定存在哈密顿回路的,并实际上存在多个回路,这里需要求出权重最大的回路,因为两个字符串之间的复用字符的个数就可以看作是权重,可以复用的字符越多,表示最终得到的字符串就会越短。对于 TSP 问题有一些高逼格的算法,比如遗传算法、蚁群算法、模拟退火算法、粒子群算法,当然这里不会讲,不是对力扣不尊重,而是没有必要,这里只讲两种解法,一种是经过剪枝优化的穷举法,另一种是动态规划 Dynamic Programming。

先来看经过剪枝优化的穷举法,这里参考了花花酱的帖子。首先来解决复用字符个数计算的问题,为了避免重复计算,可以直接计算任意两个字符串之间的复用字符的个数,用一个二维数组 overlap 表示,其中 overlap[i][j] 表示字符串 A[i] 和 A[j] 之间的复用字符的个数,比如 abc 和 bca 的复用个数是2,注意 overlap[j][i] 不一定等于 overlap[i][j],比如 bca 和 abc 的复用字符个数就是1个。更新 overlap 数组的方法就是遍历任意两个字符串的组合,跳过i和j相等的地方,然后就是从短的字符串的末尾开始查找,一个一个字符的比较,例如 abc 和 bca,比较是顺序是 abc 和 bca,bc 和 bc,c 和 b,其实最后的 c 和 b 是不用比的,当比到中间的 bc 时就可以断开了,因为长度是按从大到小的顺序比的,通过这种方法就可以算出任意两个字符串之间的复用字符个数了。接下来就是要找出最优的排序了,使用递归遍历,使用 cur 来记录当前已经遍历到的字符串的个数,used 利用二进制来记录使用过的字符串,curLen 记录当前超级字符串的长度,mn 是全局最优解的长度,order 是当前的排列顺序,best_order 是全局最优的排列顺序,变量还真不少呢。进入递归函数,其实就比较常规了,首先是一个剪枝优化,若当前长度 curLen 大于全局最优长度 mn 时,直接返回,不需要再遍历了,因为后面只会增加长度。然后就是若 cur 等于n了,说明所有的字符串都使用了,当前一定是最优的,因为不是最优的情况已经被剪掉了,没法遍历到最后面的,所以此时用 curLen 更新 mn,用 order 更新 best_order,并返回即可。否则的话就从开头遍历数组A,若当前字符串已经使用过了,则跳过。这里用的 trick 是利用 used 的二进制数的对应位跟数组A中的位置相对应,为1的话表示使用过了,为0则表示没用过。若没用过,则将当前位置加入 order,进行下一个位置的递归,下一个位置的当前长度更新比较复杂,这里用一个新变量 nextLen 来表示,若 cur 为0,说明是第一个字符串,不用考虑复用字符,则直接带入当前遍历到的字符串的长度,否则的话是要加上当前遍历到的字符串的长度减去复用字符的个数,而这个复用字符个数需要到 overlap 中取,注意坐标顺序,前一个位置是 order[cur-1],这是上一个字符串在A中的位置,后一个位置就是i,这样取出的才是正确的。还有就是别忘了更新 used 的对应位为1。得到最优排序之后,最后只要生成这个超级串就行了,这算是最简单的一步了,因为知道了任意两个相邻的字符串,也知道其之间的复用字符个数,生成最终的超级串就很容易了,参见代码如下:

解法一:

class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        int n = A.size(), mn = INT_MAX;
        vector<int> order(n), best_order;
        vector<vector<int>> overlap(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                for (int k = min(A[i].size(), A[j].size()); k > 0; --k) {
                    if (A[i].substr(A[i].size() - k) == A[j].substr(0, k)) {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }
        helper(A, overlap, 0, 0, 0, mn, order, best_order);
        string res = A[best_order[0]];
        for (int k = 1; k < n; ++k) {
            int i = best_order[k - 1], j = best_order[k];
            res += A[j].substr(overlap[i][j]);
        }
        return res;
    }
    void helper(vector<string>& A, vector<vector<int>>& overlap, int cur, int used, int curLen, int& mn, vector<int>& order, vector<int>& best_order) {
        if (curLen >= mn) return;
        if (cur == A.size()) {
            mn = curLen;
            best_order = order;
            return;
        }
        for (int i = 0; i < A.size(); ++i) {
            if (used & (1 << i)) continue;
            order[cur] = i;
            int nextLen = (cur == 0) ? A[i].size() : curLen + A[i].size() - overlap[order[cur - 1]][i];
            helper(A, overlap, cur + 1, used | (1 << i), nextLen, mn, order, best_order);
        }
    }
};

下面这种 DP 解法主要参考了 reimu 大神的帖子,这里使用一个二维数组 dp,其中 dp[i][j] 表示 mask 为i,且结尾是 A[j] 的超级串,注意这里不是长度,而是直接保存的超级串本身。这里的 mask 跟上面解法中的 used 很像,都是利用二进制中上的位来表示数组A中的某个位置上的字符是否被使用了。既然A中有n个数字,所以有n位的二进制数就是 2^n,这就是 mask 的大小范围,因为是二维数组,每一个 mask 都对应一个长度为n的一维字符串数组,每一个对应的位置表示最后面的字符串是数组A中对应位置的字符串。这里还是要用一个跟上面一样的 overlap 数组,来得到任意两个字符串之间的复用字符个数,可以参考上面的讲解。接下来是要给 dp 数组初始化,因为数组中的每个字符串都有可能是超级串的开头,所以要初始化各种情况,一旦使用了某个字符串,要在 mask 中标记对应的位置,因为目前只有一个字符串,所以直接用 1<<i 来表示 mask,并把 A[i] 加上对应位置上去。初始化完成之后就要进行更新了,要遍历 mask 的所有值,从1到 1<<n,这实际上是遍历数组A的所有子序列,对于每一个 mask 值,需要遍历其二进制每一个为1的对应位的字符串,变量j从0遍历到 n-1,假如 mask 的二进制数对应的j位上为0,则说明 A[j] 字符串未被使用,直接跳过。想想此时该如何更新 dp[mask][j],其表示的含义是使用了 mask 二进制对应位为1的所有的字符串组成的超级串,且最后一个位置是 A[j],为了更新它,需要取出 A[j],并让其他所有字符串依次当作结尾字符串,则需要依次取出所有其他的字符串,变量i来从0遍历到 n-1,若此时i等于j,说明是同一个字符串,跳过这种情况。又或者 mask 的二进制数对应的i位上为0,则说明 A[i] 字符串未被使用,同样需要跳过。此时取出 A[j],则 mask 的二进制数对应的j位应该标记为0,这里通过亦或来实现 mask^(1<<j),然后此时将 A[i] 当作结尾的超级串就是 dp[mask^(1<<j)][i],然后此时要加回 A[j],不能直接加,因为可能会有复用字符,幸亏有 overlap 数组,提前计算好了,复用字符的个数是 overlap[i][j],直接将复用字符去掉,需要加上 A[j].substr(overlap[i][j]),然后用这个新的超级串跟原来的 dp[mask][j] 比较,用较短的那个来更新 dp[mask][j] 即可。最终的结果是保存在 mask 为 (1<<n)-1 的数组中的,因为所有的字符串都需要被使用,则 mask 二进制数的所有位都必须是1,在其对应的字符串数组中找到长度最短的那个返回即可,参见代码如下:

解法二:

class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        int n = A.size();
        vector<vector<string>> dp(1 << n, vector<string>(n));
        vector<vector<int>> overlap(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                for (int k = min(A[i].size(), A[j].size()); k > 0; --k) {
                    if (A[i].substr(A[i].size() - k) == A[j].substr(0, k)) {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) dp[1 << i][i] += A[i];
        for (int mask = 1; mask < (1 << n); ++mask) {
            for (int j = 0; j < n; ++j) {
                if ((mask & (1 << j)) == 0) continue;
                for (int i = 0; i < n; ++i) {
                    if (i == j || (mask & (1 << i)) == 0) continue;
                    string t = dp[mask ^ (1 << j)][i] + A[j].substr(overlap[i][j]);
                    if (dp[mask][j].empty() || t.size() < dp[mask][j].size()) {
                        dp[mask][j] = t;
                    }
                }
            }
        }
        int last = (1 << n) - 1;
        string res = dp[last][0];
        for (int i = 1; i < n; ++i) {
            if (dp[last][i].size() < res.size()) {
                res = dp[last][i];
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/943

参考资料:

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

https://zxi.mytechroad.com/blog/searching/leetcode-943-find-the-shortest-superstring/

https://leetcode.com/problems/find-the-shortest-superstring/discuss/194932/Travelling-Salesman-Problem

https://leetcode.com/problems/find-the-shortest-superstring/discuss/195290/C%2B%2B-solution-in-less-than-30-lines

https://leetcode.com/problems/find-the-shortest-superstring/discuss/199029/Rewrite-the-official-solution-in-C%2B%2B

https://leetcode.com/problems/find-the-shortest-superstring/discuss/198920/Shortest-Hamiltonian-Path-in-weighted-digraph-(with-instructional-explanation)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation