LeetCode 97: Interleaving String

Problem Restatement

We are given three strings:

s1: str
s2: str
s3: str

We need to decide whether s3 can be formed by interleaving s1 and s2.

Interleaving means we take all characters from s1 and all characters from s2, while preserving the original order inside each string.

The characters may be mixed together.

For example:

s1 = "abc"
s2 = "def"

A valid interleaving is:

"adbcef"

because the characters from s1 still appear as:

a -> b -> c

and the characters from s2 still appear as:

d -> e -> f

The official problem asks whether s3 is formed by an interleaving of s1 and s2. The examples include s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" returning true, and s3 = "aadbbbaccc" returning false. The constraints allow s1.length and s2.length up to 100, and s3.length up to 200.

Input and Output

Function shape:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        ...

Examples

Example 1:

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

This is valid.

One way to read s3 is:

aa      from s1
dbbc    from s2
bc      from s1
a       from s2
c       from s1

The order inside s1 is preserved.

The order inside s2 is preserved.

Answer:

True

Example 2:

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"

This cannot be formed while preserving both source orders.

Answer:

False

Example 3:

s1 = ""
s2 = ""
s3 = ""

Both source strings are empty.

The target is also empty.

Answer:

True

First Thought: Recursion

At any point while building s3, we may take the next character from s1 or the next character from s2.

Suppose we have already used:

i characters from s1
j characters from s2

Then the next position in s3 is:

i + j

There are at most two choices:

1. If s1[i] == s3[i + j], take the next character from s1.
2. If s2[j] == s3[i + j], take the next character from s2.

A direct recursion follows this idea, but it repeats the same states many times.

So we use dynamic programming.

Key Insight

Define:

dp[i][j]

to mean:

s3[:i + j] can be formed by interleaving s1[:i] and s2[:j]

So:

The answer is:

dp[len(s1)][len(s2)]

Length Check

Before doing DP, check the total length.

if len(s1) + len(s2) != len(s3):
    return False

If the lengths do not match, s3 cannot use exactly all characters from s1 and s2.

Transition

For state dp[i][j], the last character of s3[:i + j] came from either s1 or s2.

Case 1: Last Character Came From s1

This is possible if:

i > 0

and:

s1[i - 1] == s3[i + j - 1]

Then we need the previous state:

dp[i - 1][j]

So:

dp[i][j] = dp[i][j] or dp[i - 1][j]

Case 2: Last Character Came From s2

This is possible if:

j > 0

and:

s2[j - 1] == s3[i + j - 1]

Then we need the previous state:

dp[i][j - 1]

So:

dp[i][j] = dp[i][j] or dp[i][j - 1]

Algorithm

Let:

m = len(s1)
n = len(s2)

Create:

dp = [[False] * (n + 1) for _ in range(m + 1)]

Set:

dp[0][0] = True

Then fill the table.

For every i from 0 to m, and every j from 0 to n:

1. If the next state can come from s1, use dp[i - 1][j].
2. If the next state can come from s2, use dp[i][j - 1].

Return:

dp[m][n]

Walkthrough

Use:

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

Start:

dp[0][0] = True

The first character of s3 is "a".

It can only come from s1[0], because s2[0] is "d".

So:

dp[1][0] = True

The next character of s3 is also "a".

It can come from s1[1].

So:

dp[2][0] = True

The next character is "d".

It comes from s2[0].

So:

dp[2][1] = True

The DP continues this way, always checking whether the next character can be explained by taking from s1 or from s2.

At the end:

dp[5][5] = True

So the answer is:

True

Correctness

The DP state dp[i][j] represents whether the first i + j characters of s3 can be formed from the first i characters of s1 and the first j characters of s2.

The base case dp[0][0] = True is correct because two empty prefixes form an empty prefix.

For any non-empty state, the last character of s3[:i + j] must come from either the last used character of s1[:i] or the last used character of s2[:j].

If it comes from s1, then s1[i - 1] must equal s3[i + j - 1], and the previous characters must form a valid interleaving represented by dp[i - 1][j].

If it comes from s2, then s2[j - 1] must equal s3[i + j - 1], and the previous characters must form a valid interleaving represented by dp[i][j - 1].

The transition checks exactly these two cases.

Therefore, by induction over i + j, every DP entry is correct. The final entry dp[m][n] answers whether all of s1 and all of s2 form all of s3.

Complexity

Let:

m = len(s1)
n = len(s2)

Implementation

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

                if j > 0 and s2[j - 1] == s3[i + j - 1]:
                    dp[i][j] = dp[i][j] or dp[i][j - 1]

        return dp[m][n]

Code Explanation

First store the string lengths:

m = len(s1)
n = len(s2)

If the total length differs, return immediately:

if m + n != len(s3):
    return False

Create the DP table:

dp = [[False] * (n + 1) for _ in range(m + 1)]

The empty prefixes match:

dp[0][0] = True

Then fill every state:

for i in range(m + 1):
    for j in range(n + 1):

If the last character came from s1:

if i > 0 and s1[i - 1] == s3[i + j - 1]:
    dp[i][j] = dp[i][j] or dp[i - 1][j]

If the last character came from s2:

if j > 0 and s2[j - 1] == s3[i + j - 1]:
    dp[i][j] = dp[i][j] or dp[i][j - 1]

Finally:

return dp[m][n]

Space-Optimized Implementation

Since each row only depends on the previous row and the current row, we can use a one-dimensional DP array.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)

        if m + n != len(s3):
            return False

        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    continue

                from_s1 = (
                    i > 0
                    and dp[j]
                    and s1[i - 1] == s3[i + j - 1]
                )

                from_s2 = (
                    j > 0
                    and dp[j - 1]
                    and s2[j - 1] == s3[i + j - 1]
                )

                dp[j] = from_s1 or from_s2

        return dp[n]

Space complexity becomes:

Testing

def run_tests():
    s = Solution()

    assert s.isInterleave("aabcc", "dbbca", "aadbbcbcac") is True
    assert s.isInterleave("aabcc", "dbbca", "aadbbbaccc") is False
    assert s.isInterleave("", "", "") is True

    assert s.isInterleave("", "abc", "abc") is True
    assert s.isInterleave("abc", "", "abc") is True
    assert s.isInterleave("abc", "def", "adbcef") is True
    assert s.isInterleave("abc", "def", "abdecf") is True
    assert s.isInterleave("abc", "def", "abdfec") is False
    assert s.isInterleave("aa", "ab", "aaba") is True
    assert s.isInterleave("aa", "ab", "abaa") is True

    print("all tests passed")

run_tests()

Test meaning: