Approach Summary
dp[i][j] = true if s1[0..i) and s2[0..j) interleave to form s3[0..i+j). Transition: use s1[i-1] or s2[j-1] if it matches s3[i+j-1].
How to Recognize This Pattern
- "Does s3 = interleave of s1 and s2"
- 2D DP on lengths — each cell extends one string or the other
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
String Dynamic Programming BFS