Find the Shortest Superstring — LeetCode 943 Python Solution
HardBit ManipulationArrayStringDynamic ProgrammingBitmask
- Problem
- #943
- Pattern
- Bit Manipulation
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- words = ["alex","loves","leetcode"]
- Output
- "alexlovesleetcode"
- Explanation
- All permutations of "alex","loves","leetcode" would also be accepted.
Python solution
Python
class Solution:
def shortestSuperstring(self, words: List[str]) -> str:
n = len(words)
g = [[0] * n for _ in range(n)]
for i, a in enumerate(words):
for j, b in enumerate(words):
if i != j:
for k in range(min(len(a), len(b)), 0, -1):
if a[-k:] == b[:k]:
g[i][j] = k
break
dp = [[0] * n for _ in range(1 << n)]
p = [[-1] * n for _ in range(1 << n)]
for i in range(1 << n):
for j in range(n):
if (i >> j) & 1:
pi = i ^ (1 << j)
for k in range(n):
if (pi >> k) & 1:
v = dp[pi][k] + g[k][j]
if v > dp[i][j]:
dp[i][j] = v
p[i][j] = k
j = 0
for i in range(n):
if dp[-1][i] > dp[-1][j]:
j = i
arr = [j]
i = (1 << n) - 1
while p[i][j] != -1:
i, j = i ^ (1 << j), p[i][j]
arr.append(j)
arr = arr[::-1]
vis = set(arr)
arr.extend([j for j in range(n) if j not in vis])
ans = [words[arr[0]]] + [words[j][g[i][j] :] for i, j in pairwise(arr)]
return ''.join(ans)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n·m) (typical) |
| Space | O(n·m) or optimized auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 943. Find the Shortest Superstring is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 943. Find the Shortest Superstring?
- LeetCode 943. Find the Shortest Superstring is rated Hard on LeetCode.
- What topics does LeetCode 943. Find the Shortest Superstring cover?
- LeetCode 943. Find the Shortest Superstring is tagged Bit Manipulation, Array, String, Dynamic Programming and Bitmask on LeetCode.