Description
Determine whether s3 can be formed by interleaving all characters of s1 and s2 while preserving the order within each source. Strings contain lowercase English letters.
Solution
def is_interleave(s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
dp = [False] * (len(s2) + 1)
dp[0] = True
for j in range(1, len(s2) + 1):
dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, len(s1) + 1):
dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
for j in range(1, len(s2) + 1):
ch = s3[i + j - 1]
dp[j] = (dp[j] and s1[i - 1] == ch) or (dp[j - 1] and s2[j - 1] == ch)
return dp[-1]Examples
Example 1
- Input
["aabcc","dbbca","aadbbcbcac"]- Output
true
A valid merge preserves both source orders.
Example 2
- Input
["aabcc","dbbca","aadbbbaccc"]- Output
false
The necessary source ordering cannot be preserved.
Example 3
- Input
["","",""]- Output
true
Empty sources form an empty result.
Approach
Reject mismatched total lengths. A rolling DP row records whether prefixes of s1 and s2 can form the corresponding prefix of s3. Each state may consume the last character from either source if it matches.
Time & space
O(mn + m + n) time and O(n) auxiliary space, where m and n are the lengths of s1 and s2.