[LeetCode] 943. Find the Shortest Superstring

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)