⚡Flashcard Drill➔
NeetCode #723LC-97Medium2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#723 · #97 · Interleaving String(交错字符串)

📌 Problem Statement & Constraints

Given strings s1, s2, and s3, return true if s3 is formed by interleaving s1 and s2 while preserving the relative order of the characters within each. Constraints: 0 <= s1.length, s2.length <= 100, 0 <= s3.length <= 200, lowercase English letters.

💡 Core Algorithmic Approaches

  1. First check that len(s1) + len(s2) == len(s3); otherwise the answer is immediately false.
  2. dp[i][j] is true when s3[0..i+j-1] is an interleaving of s1[0..i-1] and s2[0..j-1].
  3. The last character of s3 came from either s1 or s2, giving two possible transitions.
  4. So dp[i][j] is true when the last character matches s1[i-1] and dp[i-1][j] holds, or matches s2[j-1] and dp[i][j-1] holds.

💻 Benchmark Python3 Implementation

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    continue
                from_s1 = i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
                from_s2 = j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
                dp[i][j] = from_s1 or from_s2
        return dp[m][n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one state per pair of prefixes.
💾 Space Complexity
O(m * n), reducible to O(n) with a rolling row.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping the length check: if the lengths do not add up, the answer is false before any DP.
  • Indexing s3 with i + j: the combined length is i + j, so the last character sits at i + j - 1.
  • Checking only one source: a valid interleaving may take the last character from either string.
  • Assuming a greedy match works: a locally valid choice can dead-end, so the full DP is required.
⚡
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