LeetCode 943: Find the Shortest Superstring
Problem Description
Explanation
To solve this problem, we can use a bitmask dynamic programming approach. We can represent each word as a bitmask, where each bit corresponds to a character in the word. We can then create a graph where each node represents a word and each edge represents the overlap between two words.
The idea is to find the shortest superstring by finding the shortest Hamiltonian path in the graph. We can use the traveling salesman problem (TSP) approach to find the shortest path that visits all nodes exactly once and returns to the starting node.
Solutions
class Solution {
public String shortestSuperstring(String[] words) {
int n = words.length;
int[][] overlap = new int[n][n];
// Calculate overlap between each pair of words
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
overlap[i][j] = getOverlap(words[i], words[j]);
}
}
int[][] dp = new int[1 << n][n];
int[][] parent = new int[1 << n][n];
for (int mask = 1; mask < (1 << n); mask++) {
Arrays.fill(dp[mask], Integer.MAX_VALUE / 2);
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
if (mask == (1 << i)) {
dp[mask][i] = words[i].length();
} else {
for (int j = 0; j < n; j++) {
if (i != j && (mask & (1 << j)) > 0) {
int len = dp[mask ^ (1 << i)][j] + words[i].length() - overlap[j][i];
if (len < dp[mask][i]) {
dp[mask][i] = len;
parent[mask][i] = j;
}
}
}
}
}
}
}
int minLen = Integer.MAX_VALUE;
int last = -1;
for (int i = 0; i < n; i++) {
if (dp[(1 << n) - 1][i] < minLen) {
minLen = dp[(1 << n) - 1][i];
last = i;
}
}
StringBuilder sb = new StringBuilder();
int mask = (1 << n) - 1;
while (mask > 0) {
int prev = parent[mask][last];
if (prev < 0) {
sb.insert(0, words[last]);
} else {
sb.insert(0, words[last].substring(overlap[prev][last]));
}
mask ^= (1 << last);
last = prev;
}
return sb.toString();
}
private int getOverlap(String s1, String s2) {
for (int i = 0; i < s1.length(); i++) {
if (s2.startsWith(s1.substring(i))) {
return s1.length() - i;
}
}
return 0;
}
}Related LeetCode Problems
Loading editor...