Use DFS to reconstruct the interleaving string. Use memorization to avoid duplicate validation.
Time Complexity = O ( M * N ) M = len(s1), N = len(s2)
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
@lru_cache(maxsize = None)
def dfs(i, j, k):
if k >= len(s3):
return i == len(s1) and j == len(s2)
if i < len(s1) and s3[k] == s1[i]:
if dfs(i + 1, j, k + 1):
return True
if j < len(s2) and s3[k] == s2[j]:
if dfs(i, j + 1, k + 1):
return True
return False
return dfs(0, 0, 0)
No comments:
Post a Comment