假设我们有一个字符串数组A，我们必须找到任何最小的字符串，其中包含A中的每个字符串作为子字符串。我们还可以假设A中的任何字符串都不是A中另一个字符串的子字符串。
因此，如果输入类似于[“ dbsh”，“ dsbbhs”，“ hdsb”，“ ssdb”，“ bshdbsd”]，则输出将为“ hdsbbhssdbshdbsd”
为了解决这个问题，我们将遵循以下步骤-
定义一个函数calc()，这将需要a，b，
对于初始化i：= 0，当i <a的大小时，更新（将i增加1），执行-
返回b的大小-a + i的大小
如果从索引i到结尾的a的子串位于b的开头，则-
b的返回值
从主要方法中，执行以下步骤
ret：=空字符串
n：= A的大小
定义一个大小为nxn的2D数组图-
graph [i，j]：= calc（A [i]，A [j]）
graph [j，i]：= calc（A [j]，A [i]）
对于初始化j：= 0，当j <n时，更新（将j增加1），执行-
定义大小为2 ^ nx n的数组dp。
定义大小为2 ^ nx n的数组路径。
minVal：= inf
最后：= -1
对于初始化i：= 0，当i <2 ^ n时，更新（将i增加1），执行-
dp [i，j]：= inf
对于初始化j：= 0，当j <n时，更新（将j增加1），执行-
对于初始化i：= 0，当i <2 ^ n时，更新（将i增加1），执行-
minVal：= dp [i，j]
最后：= j
如果i AND 2 ^ j不为零，则
如果prev与0相同，则-
除此以外
上一个：= i ^（2 ^ j）
dp [i，j]：= A [j]的大小
如果prev AND 2 ^ k和df [prev，k]不是inf且df [prev，k] + graph [k，j] <dp [i，j]，则
dp [i，j]：= dp [prev，k] + graph [k，j]
路径[i，j]：= k
对于初始化k：= 0，当k <n时，更新（将k增加1），-
对于初始化j：= 0，当j <n时，更新（将j增加1），执行-
如果i与2 ^ n-1相同，并且dp [i，j] <minVal，则-
curr：= 2 ^ n-1
定义一个堆栈st
当curr> 0时，执行-
最后插入st
temp：= curr
curr：= curr-（2 ^ last）
最后：=路径[温度，最后]
i：= st的顶部元素
从st删除元素
ret：= ret + A [i]
虽然（不是st为空），请-
j：= st的顶部元素
从st删除元素
ret：= ret连接A [j]的子字符串，从（A [j]的大小-graph [i，j]到结尾）
i：= j
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calc(string& a, string& b){
for (int i = 0; i < a.size(); i++) {
if (b.find(a.substr(i)) == 0) {
return b.size() - a.size() + i;
}
}
return (int)b.size();
}
string shortestSuperstring(vector<string>& A){
string ret = "";
int n = A.size();
vector<vector<int> > graph(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = calc(A[i], A[j]);
graph[j][i] = calc(A[j], A[i]);
}
}
int dp[1 << n][n];
int path[1 << n][n];
int minVal = INT_MAX;
int last = -1;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = INT_MAX;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j))) {
int prev = i ^ (1 << j);
if (prev == 0) {
dp[i][j] = A[j].size();
} else {
for (int k = 0; k < n; k++) {
if ((prev & (1 << k)) && dp[prev][k] !=
INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < minVal) {
minVal = dp[i][j];
last = j;
}
}
}
int curr = (1 << n) - 1;
stack<int> st;
while (curr > 0) {
st.push(last);
int temp = curr;
curr -= (1 << last);
last = path[temp][last];
}
int i = st.top();
st.pop();
ret += A[i];
while (!st.empty()) {
int j = st.top();
st.pop();
ret += (A[j].substr(A[j].size() - graph[i][j]));
i = j;
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
cout << (ob.shortestSuperstring(v));
}{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}输出结果
hdsbbhssdbshdbsd