⚡Flashcard Drill➔
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

  1. The shortest common supersequence has length m + n - LCS(str1, str2): the longest common subsequence is written once instead of twice.
  2. Build the LCS DP table dp[i][j] = LCS length of str1[:i] and str2[:j].
  3. 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.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems