[LeetCode] Find the Shortest Superstring

943. Find the Shortest Superstring

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public:
string shortestSuperstring(vector<string>& words) {
int n = words.size();
vector<vector<int>> dist(n, vector<int>(n));
vector<vector<int>> dp(1<<n, vector<int>(n, INT_MAX));
vector<vector<int>> path(1<<n, vector<int>(n));

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dist[i][j] = getDist(words[i], words[j]);

for(int mask = 1; mask < 1<<n; mask++) {
for(int inc = 0; inc < n; inc++) {
if(mask & (1<<inc)) {
int rmMask = mask ^ (1<<inc);
if(rmMask == 0) {
dp[mask][inc] = words[inc].length();
} else {
for(int i = 0; i < n; i++) {
if(dp[rmMask][i] != INT_MAX and dp[rmMask][i] + dist[i][inc] < dp[mask][inc]) {
dp[mask][inc] = dp[rmMask][i] + dist[i][inc];
path[mask][inc] = i;
}
}
}
}
}
}

int mi = INT_MAX, last = -1, mask = (1<<n) - 1;
for(int i = 0; i < n; i++) {
if(dp[mask][i] < mi) {
mi = dp[mask][i];
last = i;
}
}

vector<int> seq;
while(mask) {
seq.push_back(last);
int nMask = mask ^ (1<<last);
last = path[mask][last];
mask = nMask;
}
int from = seq.back();
string res = words[from];
seq.pop_back();
while(!seq.empty()) {
int to = seq.back();
seq.pop_back();
res += words[to].substr(words[to].length()-dist[from][to]);

from = to;
}
return res;
}

int getDist(string& from, string& to) {
for(int i = 1; i < from.length(); i++) {
bool included = true;
for(int stFrom = i, stTo = 0; stTo < to.length() and stFrom < from.length() and included; stFrom++, stTo++) {
if(from[stFrom] != to[stTo])
included = false;
}
if(included) {
return to.length() - (from.length() - i);
}
}
return to.length();

}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/17/PS/LeetCode/find-the-shortest-superstring/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.