题目大意：
最短超级串
给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。
我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。
示例 1：
输入：["alex","loves","leetcode"] 输出："alexlovesleetcode" 解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：
输入：["catg","ctaagt","gcta","ttca","atgcatc"] 输出："gctaagttcatgcatc"
提示：
1 <= A.length <= 121 <= A[i].length <= 20
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=943
解题思路分析：
这道题要求出给定字符串数组的最短超级串。什么是超级串？英文原题中为Super String。听起来很不明觉厉，但实际上并没有那么神秘，简单来说，对于多个单词来讲，如果存在这样一个字符串，使得每个单词都能在这个字符串中找到一串连续的并与自身相同的子字符串的话，那么这个字符串就是这些单词的超级串。举例来说，单词”abc”，”cde”，”def”，他们最直观的超级串就是将三个单词连在一起，即：”abccdedef”，当然这并不是最短超级串，因为每个单词的首尾存在重复的部分，将这些部分合并之后才是最优解，所以应为：”abcdef”。
回到本题，这道题是Hard题目，自己写了几遍，代码量始终不能精简下来。先说下大体的逻辑，分三步：
- 先对数据进行预处理。将所有单词两两组合，记录下他们之间的重合部分有多少。这里需要注意，任何2个单词之间的组合有两种，比如字符串A和B，我们不仅要看A+B，也要看B+A。比如”aabc”和”caa”，如果是aabc + caa，那么他们的重合区间长度为1（字符c），合并后为”aabcaa”，反过来的话，重合长度为2（aa），因此caa + aabc = “caabc”
- 预处理之后，我们知道了所有2个单词组合时能省下的空间（重合部分），因此将所有单词组合到一起之后，肯定是总重合区间越长越好。这时我们可以将每个单词看做一个节点，任何节点间都可以双向连接，连接的路径为他们之间的重合长度。我们使用dfs搜索找到一条最优路径。
- 找到最优路径后，我们只需要按照路径将单词组合起来，同时参照预处理时得到的重合长度，将重复部分删除即可。
我们再详细看下每一步的实现方法（代码）。
一，预处理操作。
// 定义一个数组存储每两个单词间的重合距离。
// cost[i][j] 代表：单词i与单词j间的重合距离
int[][] cost = new int[length][length];
// 循环所有两两组合，此处时间复杂度为数组长度的平方
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
// i和j相同时说明是同一单词，没有重合。
if (i == j) {
continue;
}
// 判断重合距离。循环的终止条件是任何一个字符串遍历结束。
for (int k = 1; k <= A[i].length() && k <= A[j].length(); k++) {
// 比较第一个字符串后k位与第二个字符串前k位是否相同
if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k))) {
// 如果相同，则说明当前的k位是重合的。
// 但并不一定是最长重合范围，因此需要继续循环
cost[i][j] = k;
}
}
}
}二，预处理之后要进行最优路径搜索，我们这里采用dfs（深度优先搜索）来递归路径。
int maxCost = Integer.MIN_VALUE; // 用于记录搜索时找到的最大重合距离
int[] best; // 用于记录能够产生最大重合距离时的路径（单词排序路径的下标列表）
// 参数解释：
// int[] temp：用于记录路径。如果为最优路径，则将次数组赋值到best
// int tempIndex：当前路径走到第几步
// int[][] cost：预处理操作时得到的每两个单词间的重合距离
// int currentCost：当前路径能够得到的重合距离，如果此值大于maxCost，为当前最优
// boolean[] visited，记录访问过的节点，避免选择到重复单词（防止路径死循环）
private void dfs(int[] temp, int tempIndex, int[][] cost, int currentCost, boolean[] visited) {
// tempIndex等于数组长度时，说明所有单词都遍历结束。路径到达终点
if (tempIndex == length) {
// 如果此路径的总重合距离大于maxCost
if (currentCost > maxCost) {
// 更新maxCost
maxCost = currentCost;
// 并将此路径保存至best数组
// 注意此处需要用到Arrays#copyOf，如果直接等号赋值，
// 后面更改temp时，best也会同时被篡改。
best = Arrays.copyOf(temp, length);
}
return;
}
// 从数组中顺序取出一个单词添加到路径上
for (int i = 0; i < length; i++) {
// 这里只访问当前路径上尚未被选择过的单词
if (!visited[i]) {
// 得到一个临时tempCost（总重合距离）
// 如果为路径中第一步，那么tempCost为0
// 否则，tempCost的值应为之前的值加上当前节点与前一节点间的重合距离
int tempCost = tempIndex == 0 ? 0 : currentCost + cost[temp[tempIndex - 1]][i];
// 将当前节点的下标加入到路径中
temp[tempIndex] = i;
// 将当前节点设置为已访问过
visited[i] = true;
// 递归进入路径下一步
dfs(temp, tempIndex + 1, cost, tempCost, visited);
// 为了不影响之后的循环，将已访问状态变为未访问
visited[i] = false;
}
}
}对于已经十分了解dfs的同学，这个逻辑并不难理解，这段代码应该属于dfs查找时的常规操作。简单啰嗦一下，递归操作是在为一条路径找到所有节点，循环操作则是在找不同的路径。
三，利用找到的最优路径，组合出超级串。这一步操作比较简单，这里略过。
看到这里，本题思路基本上完成，但残念的是在leetcode提交之后竟然超时。。。
我想在面试的时候，如果能做到这一步，基本上面试官也不会再为难我们，算不上满分，至少及格应该没有问题。不过我们还是要分析一下超时的原因，dfs实际上接近暴力解的时间复杂度，在这里我们需要对深度搜索进行剪枝，或者说我们需要用一个memo数组来记录下已经做过的计算，当遇到相同计算时可以参照之前的结果，避免大量重复劳动。
这样说可能会比较抽象，那么对于上面的解法，哪些属于重复计算呢？我们来举例说明：
比如有10个单词，我们已经遍历过了前三个单词，下标顺序为0 -> 1 -> 2，已知这时当前的总重合范围为5，接下来，当我们我们在查找到路径1 -> 0 -> 2时，得到的总重合范围仅为3，小于之前的5，所以当前路径就没有必要继续递归下去了。原因很简单，不论是0-1-2或是1-0-2，这两条线路都是遍历完了前三个单词，并且当前位置为2，也就是说剩下的7个单词所能产生的最大重合范围是一致的，后者已经无法再超越前者产生更优解，因此此处可以剪枝。
通过这个思路，我们可以利用已经遍历过的节点集合与当前节点组合起来作为key，value中存储下这种情况下能产生的当前最优解，之后在遍历到相同情况时，只需要与这个临时最优解进行比较，小于等于的情况都可以剪枝，大于的话则需要更新最优解并继续向下递归。
那么，问题来了，这个key听起来有些复杂，已经遍历过的节点集合与当前节点听起来信息量好大，如何写成一个key呢？这里我们利用一个二维int数组来实现，定义：
int[][] memo; // ex. memo[i][j] = 5
这里下标i代表已经走过的节点集合，j表示当前节点。j很好理解，对于i，我们如何将节点集合用一个int数字来表示？这里则需要用到位操作计算。由于本博客的文章第一次涉及到位运算的讲解，这里还要多啰嗦几句。
比如在十个节点中，我们已经遍历过节点0，2，6，9（剩下1，3，4，5，7，8没有遍历），那么我们可以用一串2进制的0和1表示该节点是否遍历过，则本例可以表示为：
int j = 1001000101
从右向左，值为1的部分分别代表了0，2，6，9四个节点已经遍历过。我们将这个2进制数变换为十进制数存入变量i，就可以了。
接下来，我们看看如何生成这个二进制数。还是以0，2，6，9为例，位运算时，如果想将某一位赋值成1，可以利用左位移操作，符号为<<（两个小于号）。比如我们想左位移3位，可写成， 1 << 3，这样会得到：1000，回到本例：
j |= 1 << 0 // 1 标记下标为0的元素已经遍历过 j |= 1 << 2 // 101 标记下标为2的元素已经遍历过 j |= 1 << 6 // 1000101 标记下标为6的元素已经遍历过 j |= 1 << 9 // 1001000101 标记下标为9的元素已经遍历过
这里还用到了或运算来拼接之前的结果，或运算是比较同位的两个数，1或1为1，0或0为0，1或0为1，利用这个特性可以完美的组合之前的值。比如：
101 | 1 << 6 // 即： 101 | 1000000 // 101 // 1000000 // 1000101
这样，可以大幅优化本题的解题时间。最后附上完整代码。
int length;
int[][] memo;
public String shortestSuperstring(String[] A) {
length = A.length;
int path = 0;
for (int i = 0; i < length; i++) {
path += (1 << i);
}
memo = new int[path + 1][length];
int[][] cost = new int[length][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (i == j) {
continue;
}
for (int k = 1; k <= A[i].length() && k <= A[j].length(); k++) {
if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k))) {
cost[i][j] = k;
}
}
}
}
dfs(new int[length], 0, cost, 0, new boolean[length], 0);
String res = A[best[0]];
for (int i = 1; i < length; i++) {
int costValue = cost[best[i - 1]][best[i]];
res += A[best[i]].substring(costValue);
}
return res;
}
int maxCost = Integer.MIN_VALUE;
int[] best;
private void dfs(int[] temp, int tempIndex, int[][] cost, int currentCost, boolean[] visited, int path) {
if (tempIndex == length) {
if (currentCost > maxCost) {
maxCost = currentCost;
best = Arrays.copyOf(temp, length);
}
return;
}
for (int i = 0; i < length; i++) {
if (!visited[i]) {
int tempCost = tempIndex == 0 ? 0 : currentCost + cost[temp[tempIndex - 1]][i];
int tempPath = (path | (1 << i));
int maxCost = memo[tempPath][i];
if (maxCost > 0 && tempCost <= maxCost) {
continue;
}
temp[tempIndex] = i;
memo[tempPath][i] = tempCost;
visited[i] = true;
dfs(temp, tempIndex + 1, cost, tempCost, visited, tempPath);
visited[i] = false;
}
}
}本解用时90ms。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-943-find-the-shortest-superstring-解题思路分析/