LeetCode 97 · 2-D DP

Interleaving String, explained with a picture

Braiding two ribbons into one.

Medium2-D DP
▶ Watch it step by step

The problem

Given strings A, B and C, decide whether C can be made by interleaving A and B: weaving them together while keeping each one’s letters in their original order.

Input:  A = "aabcc", B = "dbbca", C = "aadbbcbcac"
Output: true

Picture it

Picture braiding two ribbons into one. The table’s cell (i, j) asks: can the first i letters of A and the first j letters of B make the first i + j letters of the braid? We can get there from above (the last letter came from A and it matches) or from the left (it came from B and matches).

How to recognise it

  • Two sequences must be merged into a third while each keeps its own internal order.
  • At every step of building the result, there are two choices: take the next letter from A or from B.
  • A greedy pick can be wrong, because both A and B may offer the same next letter.
  • The state is how much of A and how much of B has been used, which also fixes how much of C has been explained.
  • Lengths up to 100 and 200 rule out trying every way to weave the strings.

Start with brute force

C has m + n letters, and an interleaving decides which m of those positions come from A. Try every choice of those positions and check whether the letters match.

from itertools import combinations

def interleave_brute(a, b, c):
    if len(a) + len(b) != len(c):
        return False
    n = len(c)
    for pos in combinations(range(n), len(a)):    # positions taken from a
        from_a = set(pos)
        ai, bi = iter(a), iter(b)
        if all((next(ai) if k in from_a else next(bi)) == c[k] for k in range(n)):
            return True
    return False

There are C(m + n, m) choices, each checked in O(m + n). With m = n = 100 that is about 9 × 10^58 choices. Space is O(m + n).

From brute force to the idea

  1. Find the waste. Many different weavings reach the same point: "I have used i letters of A and j of B". The rest of the problem depends only on (i, j).
  2. C is already pinned down. If i letters of A and j of B are used, exactly i + j letters of C have been explained. So no third index is needed.
  3. Define the table. ok[i][j] is True if the first i letters of A and the first j letters of B can weave into the first i + j letters of C.
  4. Two ways in. The last letter of that prefix of C, c[i+j-1] (called k in the code), came either from A or from B. If it came from A, then a[i-1] must equal it and ok[i-1][j] must be True. If from B, then b[j-1] must equal it and ok[i][j-1] must be True. Either way makes the cell True.
  5. Start and answer. ok[0][0] is True (nothing used, nothing to explain), and ok[m][n] is the answer. A first check that len(a) + len(b) == len(c) rejects hopeless inputs at once.

This is the key idea: the pair (i, j) is enough to know where you are in C, so a table of m × n booleans replaces the exponential search.

The key idea

dp[i][j] = (dp[i−1][j] and A[i−1] == C[i+j−1]) or (dp[i][j−1] and B[j−1] == C[i+j−1]). O(m × n).

Python solution

def is_interleave(a, b, c):
    if len(a) + len(b) != len(c): return False
    ok = [[False] * (len(b) + 1) for _ in range(len(a) + 1)]
    ok[0][0] = True
    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            k = i + j - 1                 # next letter of c to explain
            if i and a[i - 1] == c[k] and ok[i - 1][j]: ok[i][j] = True
            if j and b[j - 1] == c[k] and ok[i][j - 1]: ok[i][j] = True
    return ok[len(a)][len(b)]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(C(m + n, m) · (m + n)): every choice of positions is checkedO(m + n): one set of positions
DP table (shown code)O(m · n): one constant-time step per cellO(m · n): the whole table; one row would be enough for O(n)

Edge cases

  • Length mismatch: returns False immediately. Without this check the code breaks (see the quiz).
  • All three empty: returns True, since ok[0][0] is True.
  • One string empty: ("a", "", "a") is True, and ("ab", "", "ba") is False, because C must equal the other string.
  • Greedy trap: "aa", "ab", "abaa" is True (take ab from B first, then aa from A). A greedy rule "take from A if it matches" grabs A's first letter, gets stuck and answers False, while the table answers True.
  • At cell (0, 0) the code computes k = -1, but the if i and if j tests stop c[k] from being read.

Common mistakes

  • Matching greedily (take from A whenever it matches), which fails when both strings offer the same letter.
  • Skipping the length check, so a longer C with an unused tail can be accepted.
  • Using c[i] or c[j] as the letter to explain instead of c[i + j - 1].
Your turn: count the weavings

Instead of true or false, return how many different ways C can be woven from A and B (a way is a choice of which positions of C come from A). For "a", "a", "aa" the answer is 2. Describe your approach, then write it if you like.

Compare with our answer

Same table, but each cell stores a count and the two ways in are added instead of combined with "or". Different position choices stay different even when the letters are equal.

def count_interleavings(a, b, c):
    if len(a) + len(b) != len(c):
        return 0
    ways = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    ways[0][0] = 1
    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            k = i + j - 1
            if i and a[i - 1] == c[k]:
                ways[i][j] += ways[i - 1][j]
            if j and b[j - 1] == c[k]:
                ways[i][j] += ways[i][j - 1]
    return ways[len(a)][len(b)]

count_interleavings("aa", "aa", "aaaa") is 6, ("ab", "ab", "abab") is 2, and ("", "", "") is 1. Time and space O(m · n).

A strong answer mentions: replacing True/False with counts, adding the two sources, and the count for empty strings being 1.

Check what stuck

1. You must decide whether a string C is a merge of A and B where each keeps its order, and A and B can share letters. Which approach fits best?

2. Why is the shown code O(m · n) rather than exponential?

3. The first line of the function, if len(a) + len(b) != len(c): return False, is deleted. What does the code return for a = "ab", b = "cd", c = "abcdx"?

Score 60% or more and the lesson is marked complete.