MediumNeetCode150StringDynamic Programming
Interleaving String
Check if s3 is interleaving of s1 and s2.
Examples
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true
Interleaved correctly.
Constraints
- •
0 <= s1.length, s2.length <= 100 - •
0 <= s3.length <= 200
Approaches
Try matching s1 or s2.
CodeT: O(2^(m+n)) | S: O(m+n) stack
dp[i][j] = s3[:i+j] interleaving.
CodeT: O(m*n) | S: O(m*n)
Same approach.
CodeT: O(m*n) | S: O(m*n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^(m+n)) | O(m+n) stack | Try matching s1 or s2. |
| DP 2D | O(m*n) | O(m*n) | dp[i][j] = s3[:i+j] interleaving. |
| DP 2D Optimized | O(m*n) | O(m*n) | Same approach. |
Recursion
T: O(2^(m+n))S: O(m+n) stack
Try matching s1 or s2.
DP 2D
T: O(m*n)S: O(m*n)
dp[i][j] = s3[:i+j] interleaving.
DP 2D Optimized
T: O(m*n)S: O(m*n)
Same approach.
Common Mistakes
Off-by-one in dp
Not handling empty strings
Wrong base case