```
#
# Optimal Structure
#
# i, j are 1-indexed
# M[i][j] = / True if i == j == 0
# | (s1[i] == s3[i] and M[i-1][j]) if j == 0
# | (s2[j] == s3[j] and M[i][j-1]) if i == 0
# | M[i-1][j] if s1[i] == s3[i+j-1], s2[j] != s3[i+j-1] # because the s3 shift only from s1
# | M[i][j-1] if s2[j] == s3[i+j-1], s1[i] != s3[i+j-1]
# | M[i-1][j] or M[i][j-1] if s1[i] == s2[j] == s3[i+j-1]
# \ False otherwise
#
#
#
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s1) + len(s2) != len(s3):
return False
if not len(s1):
return s3 == s2
if not len(s2):
return s3 == s1
s1_len, s2_len = len(s1), len(s2)
M = [[None] * (1+s2_len) for _ in range(1+s1_len)]
def _dfs(i, j):
if M[i][j] is None:
if i == j == 0:
M[i][j] = True
elif i == 0:
M[i][j] = (s2[j-1] == s3[j-1]) and _dfs(0, j-1)
elif j == 0:
M[i][j] = (s1[i-1] == s3[i-1]) and _dfs(i-1, 0)
elif s1[i-1] == s2[j-1] == s3[i+j-1]:
M[i][j] = _dfs(i-1, j) or _dfs(i, j-1)
elif s1[i-1] == s3[i+j-1]:
M[i][j] = _dfs(i-1, j)
elif s2[j-1] == s3[i+j-1]:
M[i][j] = _dfs(i, j-1)
else:
M[i][j] = False
return M[i][j]
return _dfs(len(s1), len(s2))
```