LeetCode #97 Medium

Interleaving String

Decide whether a string can be formed by interleaving two other strings while preserving each one's character order.

dynamic-programmingstring

02

Intuition

💡

The natural instinct is to greedily consume whichever of s1 or s2 matches the next character of s3, but that breaks the moment both strings offer the same next character -- there is no way to know locally which one to take, and a wrong guess can doom the rest even though a valid interleaving existed. This needs DP over the pair (i, j): dp[i][j] means the first i characters of s1 and the first j characters of s2 can together interleave to form the first i+j characters of s3. A cell is reachable from above if the matching s1 character lines up, or from the left if the matching s2 character lines up -- checking both possibilities is exactly what greedy single-choice consumption cannot do. Always check len(s1) + len(s2) == len(s3) first, or the DP can fill every cell and still land on a wrong answer.

03

Approach

1

Check the length invariant first

If len(s1) + len(s2) does not equal len(s3), no interleaving is possible regardless of character content, so return false immediately without building the DP table.

2

Build a 2D table of reachability

Create dp[i][j] for i from 0 to len(s1) and j from 0 to len(s2), with dp[0][0] = True as the base case: two empty prefixes trivially interleave to an empty result.

3

Fill each cell from its two possible predecessors

For each (i, j), dp[i][j] is true if dp[i-1][j] is true AND s1[i-1] matches s3[i+j-1], OR dp[i][j-1] is true AND s2[j-1] matches s3[i+j-1]. The final answer is dp[len(s1)][len(s2)], which accounts for every possible interleaving path rather than one greedy guess.

04

Solution & live demo

python

▶1class Solution:
▶2    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
▶3        m, n = len(s1), len(s2)
▶4        if m + n != len(s3):
▶5            return False
▶6        dp = [[False] * (n + 1) for _ in range(m + 1)]
▶7        dp[0][0] = True
▶8        for i in range(m + 1):
▶9            for j in range(n + 1):
▶10                if i == 0 and j == 0:
▶11                    continue
▶12                from_s1 = i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
▶13                from_s2 = j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
▶14                dp[i][j] = from_s1 or from_s2
▶15        return dp[m][n]

05

Edge cases

all three strings empty

dp[0][0] is true by definition, giving an immediate true answer

len(s1) + len(s2) != len(s3)

caught by the length check up front, returning false before any DP work

s1 or s2 empty

the DP degenerates to a straight character-by-character comparison against the non-empty string

both strings share a common next character repeatedly

the DP correctly explores both the 'from s1' and 'from s2' branches at each cell, which is exactly where greedy consumption fails

06

Complexity

Time

O(m*n)

Space

O(m*n)

m and n are the lengths of s1 and s2; every cell of the table is filled once.