Find the Shortest Superstring
update Feb 18 2019, 20:15
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 <= A.length <= 121 <= A[i].length <= 20
Basic Idea:
先上花花酱讲题的链接：https://www.youtube.com/watch?v=u_Wc4jwrp3Q
这是他视频中的slide截图，感觉很不错：
这道题本质上可以被看作哈密顿路径问题（hamiltonian path），因为我们可以将这道题的定义进行抽象：给定N个节点，每对节点之间的边有一定的weight，要求找到一条路径经过每个节点有且只有一次，且该路径总weight最小。
具体在这里，string a 和 string b 之间的 weight 就是将 b append 到 a 之后需要增加的长度。
这种问题brute force的做法是DFS，时间复杂度为 O(N!)，如果使用DP，可以利用更多的空间而使时间优化到 O(2^N)级别。这里的优化其实是显著的，Leetcode中 O(N!) 复杂度大概最多做到 N=10，而 O(2^N) 是可以做到 N=20 的。
具体的方法是DP，比较特殊的是我们需要DP数组记录不同的状态。其实在搜索路径过程中每个状态可以用它已经经过的Nodes和结尾的Node来唯一确定。只要这两者确定，我们不需要关心这些被经过的Node之间的相互顺序，这样就将排列问题优化为了一个组合问题。一般来说用一个int作为bitmap就可以表示当前路径已经经过的node（将相应位置标记为1），所以这里用到的dp数组是 int dp[1<<N][N][2]，dp[s][i][0]表示在当前已选择node集合为 s 并且该路径目前以 i 结尾的最短长度， dp[s][i][1] 则记录上一个node的index用来最终恢复路径。
Java Code:
class Solution {
public String shortestSuperstring(String[] A) {
int V = A.length;
// 算每个string a和其他string b相连之后增加的 length
int[][] dist = new int[V][V];
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
String a = A[i], b = A[j]; // 拼ab，算长度
int commonLen = Math.min(a.length(), b.length());
while (commonLen > 0 &&
!a.substring(a.length() - commonLen).equals(b.substring(0, commonLen))) {
commonLen--;
}
dist[i][j] = b.length() - commonLen;
// System.out.println(a + " " + b + " " + dist[i][j]);
}
}
// dp[i][j] 表示以 binary mask i 表示的前缀节点组合并且以 A[j] 结尾的路径，
// 其最小长度为 dp[i][j][0]
// dp[i][j][1] 存放的是parent的index，因为我们最终要找到一条最短路径
int[][][] dp = new int[1<<V][V][2];
// initialization
for (int i = 0; i < dp.length; ++i) {
for (int j = 0; j < V; ++j) {
dp[i][j][0] = Integer.MAX_VALUE / 2;
dp[i][j][1] = -1;
}
}
for (int i = 0; i < V; ++i) {
dp[1<<i][i][0] = A[i].length();
}
// 每种前缀节点组合
for (int s = 0; s < (1<<V); ++s) {
// 考虑每个node作为当前结尾
for (int i = 0; i < V; ++i) {
if (((1 << i) & s) == 0) continue; // 该组合s中没有node i
int prev = s & (~(1 << i)); // 之前的组合，不包括i
// 考虑每个node为之前的结尾
for (int j = 0; j < V; ++j) {
if (i == j || ((1 << j) & prev) == 0) continue;
if (dp[prev][j][0] + dist[j][i] < dp[s][i][0]) {
dp[s][i][0] = dp[prev][j][0] + dist[j][i];
dp[s][i][1] = j;
}
// System.out.println(i + " " + A[i] + " " + A[j] + " " + dp[s][i][0] + " " + dist[j][i]);
}
}
}
// 在dp[(1<<V)-1]（即所有node都被使用的组合）中找出最小的长度，并利用dp[i][j][1]得到path
int minLen = Integer.MAX_VALUE / 2, minEndNode = -1, s = (1 << V) - 1;
for (int i = 0; i < V; ++i) {
if (dp[s][i][0] < minLen) {
minLen = dp[s][i][0];
minEndNode = i;
}
}
String res = "";
int curr = minEndNode;
// System.out.println(A[minEndNode] + " " + minLen);
while (s > 0) {
int prev = dp[s][curr][1];
if (prev < 0) {
res = A[curr] + res;
return res;
} else {
int len = dist[prev][curr];
res = A[curr].substring(A[curr].length() - len) + res;
}
s &= ~(1 << curr);
curr = prev;
}
return res;
}
}Last updated