NeetCode #739LC-1092Hard2-D Dynamic Programming
← Back to All Problems#739 · #1092 · Shortest Common Supersequence(最短公共超序列)
📌 Problem Statement & Constraints
Given two strings
str1 and str2, return the shortest string that has both as subsequences. Constraints: 1 <= str1.length, str2.length <= 1000.💡 Core Algorithmic Approaches
- The shortest common supersequence has length
m + n - LCS(str1, str2): the longest common subsequence is written once instead of twice. - Build the LCS DP table
dp[i][j]= LCS length ofstr1[:i]andstr2[:j]. - Reconstruct by walking back from
(m, n): on a match, emit the shared character and step diagonally; otherwise step toward the larger DP value, emitting the character you leave behind. - Append whatever remains of either string once one index reaches 0, then reverse the collected characters.
💻 Benchmark Python3 Implementation
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
m, n = len(str1), len(str2)
# dp[i][j] = LCS length of str1[:i] and str2[:j]
dp = [[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]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# walk back to rebuild one shortest supersequence
res = []
i, j = m, n
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
res.append(str1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
res.append(str1[i - 1])
i -= 1
else:
res.append(str2[j - 1])
j -= 1
while i > 0:
res.append(str1[i - 1])
i -= 1
while j > 0:
res.append(str2[j - 1])
j -= 1
return "".join(reversed(res))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): the LCS table plus an O(m + n) reconstruction.
💾 Space Complexity
O(m * n) for the table (the output is O(m + n)).
⚠️ Interview Pitfalls & Follow-ups
- Returning the LCS itself: the supersequence must contain all characters of both strings, so the non-LCS characters must be interleaved as well.
- Appending in forward order: the reconstruction walks backwards, so the accumulated list must be reversed at the end.
- Forgetting the trailing loops: once one index reaches 0, the remaining characters of the other string still need to be emitted.
- Choosing a tie-break and not emitting the skipped character: whichever branch you take, the character you move past must be appended, or the result loses characters.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.