Interleaving String

If s3 is an interleaving of s1 and s2, then having consumed i characters of s1 and j characters of s2 must together account for exactly the first i + j characters of s3. Whether the state (i, j) is reachable does not depend on which order the characters were taken in, only on whether the next needed character of s3 can come from s1 or s2 at this point — a classic 2-D boolean DP.

Brute Force Recursion

Time O(2^(m+n))Space O(m+n)

At each pair of pointers (i, j) into s1 and s2, try consuming the next character from whichever string’s next character matches s3[i+j], and recurse.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        def rec(i: int, j: int) -> bool:
            if i == m and j == n:
                return True
            k = i + j
            take_s1 = i < m and s1[i] == s3[k] and rec(i + 1, j)
            take_s2 = j < n and s2[j] == s3[k] and rec(i, j + 1)
            return take_s1 or take_s2
        return rec(0, 0)

Each call can branch two ways, and the same (i, j) pair is reached along many different orderings of characters — exponential blow-up.

2-D DP Table (Bottom-Up)

OptimalTime O(m·n)Space O(m·n)

dp[i][j] is true if the first i + j characters of s3 can be formed by interleaving s1[0:i] and s2[0:j]. Base case dp[0][0] = True (two empty prefixes trivially interleave into an empty string). Row 0 and column 0 extend that by matching a single string against a prefix of s3 directly. Every other cell is reachable if either the last character came from s1 (dp[i-1][j] was reachable and s1[i-1] == s3[i+j-1]) or from s2 (symmetric).

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        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 i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        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):
            for j in range(1, n + 1):
                k = i + j - 1
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[k]) or \
                           (dp[i][j - 1] and s2[j - 1] == s3[k])
        return dp[m][n]

Filling the table for s1 = "ab", s2 = "ba", s3 = "abba" (a small true case, 1 = true): watch each cell pull its value from the cell above or the cell to the left, and only when the matching character lines up.

abba

dp[i][j] reachable

012

take from s1 (above)

- vs -

- = -

take from s2 (left)

- vs -

- = -

1 / 9

currentresultcomparing

Base case: zero characters from each string interleave into an empty string, so dp[0][0] is true.

Complexity: each of the (m+1)·(n+1) cells does O(1) work → O(m·n) time, O(m·n) space.

1-D Rolling Array

Time O(m·n)Space O(n)

Row i of the table only depends on row i-1 (via dp[i-1][j]) and on itself at the previous column (via dp[i][j-1]). A single 1-D array reused across rows captures both, exactly like the unique-paths rolling-array trick, as long as the update order is preserved.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [False] * (n + 1)
        dp[0] = True
        for j in range(1, n + 1):
            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
            for j in range(1, n + 1):
                k = i + j - 1
                dp[j] = (dp[j] and s1[i - 1] == s3[k]) or (dp[j - 1] and s2[j - 1] == s3[k])
        return dp[n]

Same O(m·n) time, but only one row of length n + 1 is kept — O(n) space, matching the follow-up’s target.

Interleaving String

Brute Force Recursion

2-D DP Table (Bottom-Up)

1-D Rolling Array

More 2-D DP practice