Shortest Common Supersequence — LeetCode 1092 Python Solution
HardStringDynamic Programming
- Problem
- #1092
- Pattern
- Dynamic Programming
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
Example
- Input
- str1 = "abac", str2 = "cab"
- Output
- "cabac"
- Explanation
- str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
Python solution
Python
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
m, n = len(str1), len(str2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
ans = []
i, j = m, n
while i or j:
if i == 0:
j -= 1
ans.append(str2[j])
elif j == 0:
i -= 1
ans.append(str1[i])
else:
if f[i][j] == f[i - 1][j]:
i -= 1
ans.append(str1[i])
elif f[i][j] == f[i][j - 1]:
j -= 1
ans.append(str2[j])
else:
i, j = i - 1, j - 1
ans.append(str1[i])
return ''.join(ans[::-1])Complexity
| Measure | Complexity |
|---|---|
| Time | O(n·m) (typical) |
| Space | O(n·m) or optimized auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1092. Shortest Common Supersequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1092. Shortest Common Supersequence?
- LeetCode 1092. Shortest Common Supersequence is rated Hard on LeetCode.
- What topics does LeetCode 1092. Shortest Common Supersequence cover?
- LeetCode 1092. Shortest Common Supersequence is tagged String and Dynamic Programming on LeetCode.