# Python 48ms DP Solution with Memorization

• ``````#
#   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))``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.