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
- First check that
len(s1) + len(s2) == len(s3); otherwise the answer is immediately false. dp[i][j]is true whens3[0..i+j-1]is an interleaving ofs1[0..i-1]ands2[0..j-1].- The last character of
s3came from eithers1ors2, giving two possible transitions. - So
dp[i][j]is true when the last character matchess1[i-1]anddp[i-1][j]holds, or matchess2[j-1]anddp[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
s3withi + j: the combined length isi + j, so the last character sits ati + 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.