Core Insight A table exposes how two changing prefixes or positions depend on smaller cases.
Common Pitfall Initialize the first row and column before using neighboring cells.
Description
Check if s3 is an interleaving of s1 and s2.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m·n)
Tags
stringdynamic-programmingmemoization
Implementation Plan Translate the invariant into these small, testable moves.
- Define the row and column meaning.
- Initialize base cases.
- Fill cells in dependency order.
- Read the answer from the target cell.
def isInterleave(s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
dp[len(s1)][len(s2)] = True
for i in range(len(s1), -1, -1):
for j in range(len(s2), -1, -1):
if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
dp[i][j] = True
if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
dp[i][j] = True
return dp[0][0]