239. Interleaving String

Why this mechanism works

Two consumed counts determine the target position automatically: after i characters from first and j from second, exactly i+j target characters have been formed. A state is reachable if its last character came from a reachable predecessor in either source and matches the corresponding target character. Ambiguous equal characters require considering both alternatives.

State and boundaries

dp[i][j] means target[:i+j] can be formed from first[:i] and second[:j]. dp[0][0] is true.

Protocol

1. Reject a total-length mismatch.
2. Seed the empty-prefix state.
3. Scan all prefix pairs.
4. Accept a transition from above if the next first character matches.
5. Accept one from the left if the next second character matches.
6. Return the full-prefix state.

Visualization

first ab, second cd, target acbd
(0,0)->(1,0)->(1,1)->(2,1)->(2,2)
target progress is always i+j

Python implementation

def is_interleaving(first, second, target):
    m, n = len(first), len(second)
    if m + n != len(target):
        return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(m + 1):
        for j in range(n + 1):
            if i:
                dp[i][j] |= dp[i - 1][j] and first[i - 1] == target[i + j - 1]
            if j:
                dp[i][j] |= dp[i][j - 1] and second[j - 1] == target[i + j - 1]
    return dp[m][n]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 is_interleaving: m, n = len(first), len(second)
first='ab'; second='cd'; target='acbd'; m=2; n=2

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='acbd'; m=2; n=2; _=0

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='acbd'; m=2; n=2; _=1

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='acbd'; m=2; n=2; _=2

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[False, False, False], [False, False, False], [False, False, False]]

L6 is_interleaving: dp[0][0] = True
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]

L7 is_interleaving: for i in range(m + 1):
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]; i=0

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]; i=0; j=0

... 10 intermediate state changes omitted ...

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [True, True, False], [False, False, False]]; i=2; j=1

L10 is_interleaving: dp[i][j] |= dp[i - 1][j] and first[i - 1] == target[i + j - 1]
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [True, True, False], [False, True, False]]; i=2; j=1

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [True, True, False], [False, True, False]]; i=2; j=2

L12 is_interleaving: dp[i][j] |= dp[i][j - 1] and second[j - 1] == target[i + j - 1]
first='ab'; second='cd'; target='acbd'; m=2; n=2; dp=[[True, False, False], [True, True, False], [False, True, True]]; i=2; j=2

L2 is_interleaving: m, n = len(first), len(second)
first='ab'; second='cd'; target='adbc'; m=2; n=2

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='adbc'; m=2; n=2; _=0

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='adbc'; m=2; n=2; _=1

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='adbc'; m=2; n=2; _=2

L5 is_interleaving: dp = [[False] * (n + 1) for _ in range(m + 1)]
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[False, False, False], [False, False, False], [False, False, False]]

L6 is_interleaving: dp[0][0] = True
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]

L7 is_interleaving: for i in range(m + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]; i=0

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [False, False, False], [False, False, False]]; i=0; j=0

... 7 intermediate state changes omitted ...

L7 is_interleaving: for i in range(m + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [True, False, False], [False, False, False]]; i=2; j=2

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [True, False, False], [False, False, False]]; i=2; j=0

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [True, False, False], [False, False, False]]; i=2; j=1

L8 is_interleaving: for j in range(n + 1):
first='ab'; second='cd'; target='adbc'; m=2; n=2; dp=[[True, False, False], [True, False, False], [False, False, False]]; i=2; j=2

Why the solution is correct

Any interleaving's last character comes from exactly one source, so removing it gives one of the two predecessor states. Conversely, appending a matching source character to a valid predecessor preserves both source orders. Their boolean union therefore captures all possible interleavings.

Time and space

O(m*n+m+n) time and O((m+1)*(n+1)) table space, including empty-source boundaries.

Common mistakes

Greedily choosing first whenever both sources match can block a later valid route. A third DP axis is redundant because i+j determines target progress.

Reasoning card

Transfer exercise

Count distinct source-choice sequences instead of returning a boolean, noting that equal character values can hide different choices.