Interleaving String

Interleaving String asks whether one string can be built by zipping two others together without ever reordering either. It is a clean introduction to two-dimensional grid DP: the answer for the whole problem is assembled from the answers to smaller prefix problems stored in a table.

The slow way first

The brute-force idea: at each character of s3, try taking it from s1 or from s2, and recurse. That branches two ways at every step, giving O(2^(m+n)) time. The recursion revisits the same (i, j) prefix pair over and over, which is the tell-tale sign that we should cache results in a table.

The question to ask: how much of s3 can I build using exactly the first i characters of s1 and the first j of s2? If I know that for every smaller (i, j), the full answer falls out.

The idea: a grid of prefix answers

Let dp[i][j] be True when the first i characters of s1 and the first j characters of s2 interleave to form the first i + j characters of s3. The current target character is s3[i + j - 1]. A cell is True when we can extend a True neighbor by matching that character:

• From the top (dp[i-1][j]): we just consumed s1[i-1], so it must equal s3[i+j-1].
• From the left (dp[i][j-1]): we just consumed s2[j-1], so it must equal s3[i+j-1].

The top-left corner dp[0][0] is True (two empty prefixes make the empty string), and the answer to the whole problem is the bottom-right corner dp[m][n].

Walk through it

Step through the animation. We seed dp[0][0] = True, then fill the first row using only s2, the first column using only s1, and finally the interior by combining a top match or a left match. Green cells are True; the comparing cell is the one being decided. The True frontier flows down and right until it reaches the bottom-right corner — True, so aab and axy do interleave into aaxaby.

Pseudocode

if len(s1) + len(s2) != len(s3): return False
dp is an (m+1) x (n+1) grid of False
dp[0][0] = True
fill first row: dp[0][j] true while s2[:j] matches s3[:j]
fill first column: dp[i][0] true while s1[:i] matches s3[:i]
for each interior cell (i, j):
    k = i + j - 1                      # the s3 char we are placing
    from top:  dp[i-1][j] and s1[i-1] == s3[k]
    from left: dp[i][j-1] and s2[j-1] == s3[k]
    dp[i][j] = from_top or from_left
return dp[m][n]

The Python solution

def is_interleave(s1, s2, s3):
    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 j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            k = i + j - 1
            from_top = dp[i - 1][j] and s1[i - 1] == s3[k]
            from_left = dp[i][j - 1] and s2[j - 1] == s3[k]
            dp[i][j] = from_top or from_left
    return dp[m][n]

• The length check is a free early exit: if the lengths do not add up, no interleaving exists.
• dp[0][0] = True is the base case — both prefixes empty.
• The first row fills left to right using only s2; the first column fills top to bottom using only s1. Each stops being True the moment a character disagrees with s3.
• k = i + j - 1 is the index in s3 we are trying to place at cell (i, j).
• Line 16 is the recurrence: a cell is True if either a True cell above matched s1's char or a True cell to the left matched s2's char.
• dp[m][n] is the answer for the full strings.

Complexity

Each of the (m+1)(n+1) cells is computed once from a constant number of neighbors, so the table fills in O(m·n). The space can be squeezed to O(n) by keeping just one row, but the full grid is clearest for learning.

When this pattern shows up

Practice