Interleaving string

Determine whether a string can be formed by interleaving two other strings.

dynamic-programming strings dp 2d-dp

Given three strings `s1`, `s2`, and `s3`, write a function `is_interleave(s1: str, s2: str, s3: str) -> bool` that returns `True` if `s3` can be formed by interleaving `s1` and `s2` without changing the relative order of characters from each original string, and `False` otherwise.

An interleaving of two strings `s1` and `s2` is a new string that contains all characters from both strings, preserving the order of characters from `s1` and `s2` respectively. For example, `"aabc"` is an interleaving of `"abc"` and `"a"`.

**Function signature:** `def is_interleave(s1: str, s2: str, s3: str) -> bool:`

**Input:** Three strings `s1`, `s2`, `s3`. Each consists of lowercase English letters. Lengths are between 0 and 100 inclusive.

**Output:** Return `True` if `s3` is an interleaving of `s1` and `s2`, else `False`.

Constraints

0 <= len(s1), len(s2) <= 100; 0 <= len(s3) <= 200.
All characters are lowercase English letters.
Time complexity should be O(len(s1)*len(s2)) or better.

Example

>>> is_interleave("abc", "def", "adbcef")
True
>>> is_interleave("abc", "def", "abctdef")
False
>>> is_interleave("", "abc", "abc")
True
>>> is_interleave("aabcc", "dbbca", "aadbbbaccc")
False

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think: if s3 is formed by interleaving, then for each prefix of s3, the last character must come from the next unused character of either s1 or s2.

Use a 2D DP table where dp[i][j] indicates whether the first i characters of s1 and first j characters of s2 can interleave to form the first i+j characters of s3.

Initialize dp[0][0] = True. Fill row by row: dp[i][j] is True if (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1]).

Edge case: if len(s1)+len(s2) != len(s3), return False immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.