Pattern Recognition Drill

#132 — Interleaving String

Medium 2-D Dynamic Programming

The Problem

Given strings s1, s2, s3, determine if s3 is formed by interleaving s1 and s2.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Interleaving' → characters from s1 and s2 in order, merged
'Is s3 formed by interleaving' → 2D DP: dp[i][j] = can we form s3[:i+j] using s1[:i] and s2[:j]

Dynamic Programming

dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1]). O(mn).

Alt: DFS / Recursion

Recursive with memo on (i, j). Same O(mn) but stack overhead.

Common Trap

Check len(s1) + len(s2) == len(s3) first. If not, immediately return False.

← #131