Medium 2D Boolean DP 2-D Dynamic Programming
In plain English: Check if a third string is a valid interleaving of two other strings, keeping the order of characters from each.
dp[i][j] = can s1[:i] and s2[:j] interleave to form s3[:i+j]? Transition: dp[i][j] is True if we can extend from dp[i-1][j] by matching s1[i-1], or from dp[i][j-1] by matching s2[j-1].
Prompt
Given strings s1, s2, and s3, determine whether s3 is formed by interleaving s1 and s2 (maintaining their relative order).
Try to write it from scratch before scrolling down.
Solution
def is_interleave(s1, s2, s3):
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# dp[i][j] = True if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j]
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):
# extend from s1 (row above) or s2 (col left) if the next char matches s3
dp[i][j] = (
(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])
)
return dp[m][n]
# Test: is_interleave("aabcc", "dbbca", "aadbbcbcac") == True
# Test: is_interleave("aabcc", "dbbca", "aadbbbaccc") == False