Find the shortest superstring [Hard]
Given a set of cities and distances between every pair of cities,
- Hamiltonian cycle: find if there exists a tour that visits every city exactly once;
- Travelling salesman problem (TSP): find the shortest possible route that visits every city exactly once and returns to the starting point (i.e. find the minimum weight hamiltonian cycle).
TSP is a NP-hard problem (no polynomial time solution).
This problem is a TSP:
Given an array of strings
words, return the smallest string that contains each string inwordsas a substring. If there are multiple valid strings of the smallest length, return any of them.You may assume that no string in
wordsis a substring of another string inwords.Example 1:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
Solution 1: Naive DFS (Time Limit Exceeded)
A naive solution to get an idea on how the problem can be solved:
- Always convert string operations into integers. Construct a
mapto count number of overlapped alphabetsmap[a][b]if the string is connected as a->b; - Exhaustively use DFS to loop through all possible permutations of the nodes, and keep track of the shortest path;
- Convert integer path back to String.
class Solution {
int minCount = Integer.MAX_VALUE;
List<Integer> resultInt = new ArrayList<Integer>();
public String shortestSuperstring(String[] words) {
int[][] map = new int[words.length][words.length];
for(int i = 0; i < words.length; i ++) {
for(int j = 0; j < words.length; j ++) {
if(i == j) continue;
map[i][j] = getOverlap(words[i], words[j]);
}
}
for(int i = 0; i < words.length; i ++) {
dfs(words, map, new boolean[words.length], i, words[i].length(), new ArrayList<Integer>());
}
StringBuilder sb = new StringBuilder();
sb.append(words[resultInt.get(0)]);
for(int i = 1; i < words.length; i ++) {
String str = words[resultInt.get(i)];
int startIndex = map[resultInt.get(i - 1)][resultInt.get(i)];
sb.append(str.substring(startIndex, str.length()));
}
return sb.toString();
}
private void dfs(String[] words, int[][] map, boolean[] visited, int cur, int count, ArrayList<Integer> path){
boolean hasNext = false;
path.add(cur);
visited[cur] = true;
for(int i = 0; i < visited.length; i ++) {
if(cur == i || visited[i]) continue;
hasNext = true;
dfs(words, map, visited, i, count + words[i].length() - map[cur][i], path);
}
if(!hasNext && minCount > count) {
minCount = count;
resultInt = (ArrayList<Integer>)path.clone();
}
path.remove(path.size() - 1);
visited[cur] = false;
}
// a -> b, count the number of overlapped alphabets.
private int getOverlap(String a, String b) {
int count = 0;
for(int i = 0 ; i < a.length(); i ++) {
if(a.charAt(i) == b.charAt(0)) {
count = a.length() - i;
for(int j = i + 1; j < a.length() && j - i < b.length(); j ++) {
if(a.charAt(j) != b.charAt(j - i)) {
count = 0; break;
}
}
if(count > 0) break;
}
}
return count;
}
}The above algorithm can be improved by storing the count & integer list for the tails to reduce number of recursions. For example, given nodes 1,2,3,4,5 we have permutations:
(1) 1 -> 2 -> 3 -> 4 -> 5
(2) 1 -> 3 -> 2 -> 4 -> 5
(3) 2 -> 1 -> 3 -> 4 -> 5
(4) 2 -> 3 -> 1 -> 4 -> 5
(5) 3 -> 1 -> 2 -> 4 -> 5
(6) 3 -> 2 -> 1 -> 4 -> 5One way to optimize this algorithm is to store the count result for 4 -> 5. By doing so, we can avoid dig-ins into the two nodes (2) — (6), which can significantly reduce the time it takes to find the shortest path. This optimization technique becomes even more effective when we’re dealing with a large number of nodes. It’s similar to the idea behind using an insertion sort with a cutoff threshold in quicksort to optimize its time complexity.
Solution 2: DP and Bit Mask
class Solution {
public String shortestSuperstring(String[] A) {
int n = A.length;
int[][] graph = new int[n][n];
// build the graph
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 = new int[1 << n][n];
int[][] path = new int[1 << n][n];
int last = -1, min = Integer.MAX_VALUE;
// start TSP DP
for (int i = 1; i < (1 << n); i++) { // for all the combinations of the nodes
Arrays.fill(dp[i], Integer.MAX_VALUE);// the length =MAX_VALUE
for (int j = 0; j < n; j++) { //for each node
if ((i & (1 << j)) > 0) { // if the node is in the set. Assume i = 10010(18), j = 100(4), then set={1,4}, the node is 2. The node is not in this set
int prev = i - (1 << j); // the set without j. Assume i = 10010, j = 10 then pre = 10000
if (prev == 0) { // if j is the only one
dp[i][j] = A[j].length(); // the entire word
} else {
for (int k = 0; k < n; k++) { //try all the possible nodes before j
if (dp[prev][k] < Integer.MAX_VALUE && dp[prev][k] + graph[k][j] < dp[i][j]) { // if k is valid and the length could be reduced
dp[i][j] = dp[prev][k] + graph[k][j]; //update the result
path[i][j] = k; // update the node before j
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < min) { // if i == 11...1111 means the node set contains all the nodes, and the length is smaller
min = dp[i][j]; //update the result
last = j; //update the last node
}
}
}
// build the path
StringBuilder sb = new StringBuilder();
int cur = (1 << n) - 1;
Stack<Integer> stack = new Stack<>();
while (cur > 0) {
stack.push(last);
int temp = cur;
cur -= (1 << last);
last = path[temp][last];
}
// build the result
int i = stack.pop();
sb.append(A[i]);
while (!stack.isEmpty()) {
int j = stack.pop();
sb.append(A[j].substring(A[j].length() - graph[i][j]));
i = j;
}
return sb.toString();
}
//
private int calc(String a, String b) {
for (int i = 1; i < a.length(); i++) {
if (b.startsWith(a.substring(i))) {
return b.length() - a.length() + i;
}
}
return b.length();
}
}Reference: leetcode solution.
More readings on the hamiltonian path:
