How do you solve Find the Shortest Superstring on LeetCode?

Find the Shortest Superstring (LeetCode #943) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n^2 * 2^n) time complexity and O(n * 2^n) space complexity. Key insight: Understanding overlaps between strings is crucial for optimizing the superstring construction.

What is the brute force solution for Find the Shortest Superstring?

The brute force approach for Find the Shortest Superstring is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute force approach involves generating all possible permutations of the input strings and checking each permutation to see if it contains all the strings as substrings. This is simple but inefficient as the number of permutations grows factorially with the number of strings. The optimal Optimal Solution approach improves this to O(n^2 * 2^n).

What are the interview tips for Find the Shortest Superstring?

Clearly explain your thought process and the reasoning behind each step. Discuss edge cases and how your solution handles them. Be prepared to optimize your solution if the interviewer asks for it.

What are common mistakes when solving Find the Shortest Superstring?

Failing to account for overlaps correctly, leading to longer superstrings. Not using bitmasking effectively, which can lead to exponential time complexity.

#943

Find the Shortest Superstring

Hard

ArrayStringDynamic ProgrammingBit ManipulationBitmaskDynamic ProgrammingBitmasking

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n^2 * 2^n)
Space	O(n)	O(n * 2^n)

💡

Intuition

Time O(n^2 * 2^n)Space O(n * 2^n)

The optimal solution uses a dynamic programming approach combined with bitmasking to efficiently find the shortest superstring. This method reduces the number of combinations we need to check by storing results of overlapping substrings.

⚙️

Algorithm

3 steps

1Step 1: Create a distance matrix that stores the maximum overlap between each pair of strings.
2Step 2: Use dynamic programming with bitmasking to explore all combinations of strings, keeping track of the minimum length superstring formed.
3Step 3: Construct the shortest superstring based on the DP results.

solution.py25 lines

1def shortest_superstring(words):
2    n = len(words)
3    overlap = [[0] * n for _ in range(n)]
4    for i in range(n):
5        for j in range(n):
6            overlap[i][j] = max_overlap(words[i], words[j])
7    dp = [[float('inf'), ''] for _ in range(1 << n)]
8    dp[0] = [0, '']
9    for mask in range(1 << n):
10        for i in range(n):
11            if mask & (1 << i):
12                prev_mask = mask ^ (1 << i)
13                for j in range(n):
14                    if prev_mask & (1 << j):
15                        new_length = dp[prev_mask][0] + overlap[j][i]
16                        if new_length < dp[mask][0]:
17                            dp[mask] = [new_length, dp[prev_mask][1] + words[i][overlap[j][i]:]]
18    return dp[(1 << n) - 1][1]
19
20def max_overlap(a, b):
21    max_len = 0
22    for i in range(1, len(a) + 1):
23        if b.startswith(a[i - 1:]):
24            max_len = i
25    return max_len

ℹ

Complexity note: The time complexity is O(n^2 * 2^n) due to the DP approach with bitmasking, where n is the number of strings. The space complexity is O(n * 2^n) for storing the DP states.

1Understanding overlaps between strings is crucial for optimizing the superstring construction.
2Dynamic programming with bitmasking can significantly reduce the number of combinations to check.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.