LeetCode 943: Find the Shortest Superstring Solution
Master LeetCode problem 943 (Find the Shortest Superstring), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
943. Find the Shortest Superstring
Problem Explanation
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.
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 943 (Find the Shortest Superstring)?
This page provides optimized solutions for LeetCode problem 943 (Find the Shortest Superstring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 943 (Find the Shortest Superstring)?
The time complexity for LeetCode 943 (Find the Shortest Superstring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 943 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 943 in Java, C++, or Python.