LC 0097 [M] Interleaving String
Code with Senpai edited this page Jun 19, 2022
·
10 revisions
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if (len(s1) + len(s2)) != len(s3):
return False
dp = {}
@cache
def dfs(i, j):
# if (i, j) in dp:
# return dp[(i, j)]
if i == len(s1) and j == len(s2):
return True
choose_s1 = i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j)
choose_s2 = j < len(s2) and s2[j] == s3[i+j] and dfs(i, j+1)
# if (choose_s1 or choose_s2):
# dp[(i,j)] = True
# else:
# dp[(i,j)] = False
# return dp[(i,j)]
return (choose_s1 or choose_s2)
return dfs(0,0)
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if (len(s1) + len(s2)) != len(s3):
return False
ROWS = len(s2)
COLS = len(s1)
T = [ [0 for c in range(COLS + 1)] for r in range(ROWS + 1) ]
T[0][0] = 1
for r in range(1, ROWS + 1):
if s2[r-1] == s3[r-1] and T[r-1][0] == 1:
T[r][0] = 1
for c in range(1, COLS + 1):
if s1[c-1] == s3[c-1] and T[0][c-1] == 1:
T[0][c] = 1
for r in range(1, ROWS + 1):
for c in range(1, COLS + 1):
rc = r + c # diag
if (s2[r-1] == s3[rc-1] and T[r-1][c] == 1) or (s1[c-1] == s3[rc-1] and T[r][c-1] == 1):
T[r][c] = 1
return T[-1][-1]
footer