Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
- s = s1 + s2 + ... + sn
- t = t1 + t2 + ... + tm
- |n - m| <= 1
- The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ... Note: a + b is the concatenation of strings a and b.
A straightforward version
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
N1 = len(s1)
N2 = len(s2)
if N1 + N2 != len(s3):
return False
dp = [[False] * (N2 + 1) for _ in range(N1 + 1)]
for i in range(N1 + 1):
for j in range(N2 + 1):
dp[i][j] = (i == j == 0) or \
(i == 0 and dp[i][j - 1] and s2[j - 1] == s3[j - 1]) or \
(j == 0 and dp[i - 1][j] and s1[i - 1] == s3[i - 1]) or \
(i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \
(j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
return dp[-1][-1]
A compact version
def isInterleave(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
stack, visited = [(0, 0)], set((0, 0))
while stack:
x, y = stack.pop()
if x+y == l:
return True
if x+1 <= r and s1[x] == s3[x+y] and (x+1, y) not in visited:
stack.append((x+1, y)); visited.add((x+1, y))
if y+1 <= c and s2[y] == s3[x+y] and (x, y+1) not in visited:
stack.append((x, y+1)); visited.add((x, y+1))
return False