Description:
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Solutions: 遞歸
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1)+len(s2) != len(s3): # corner cases
return False
dp = [[None for j in range(len(s1)+1)] for i in range(len(s2)+1)]
dp[-1][-1] = True # The Destination should be True
def search(cnt,row,col):
if dp[row][col] != None:
return dp[row][col]
if row < len(s2) and s2[row] == s3[cnt] and search(cnt+1,row+1,col): # move downward
dp[row][col] = True
return True
if col < len(s1) and s1[col] == s3[cnt] and search(cnt+1,row,col+1): # move right
dp[row][col] = True
return True
dp[row][col] = False # fail to find a path
return False
return search(0,0,0)
# print("\n-------------------------")
# for d in dp:
# print(d)
Runtime: 36 ms, faster than 88.84% of Python3 online submissions for Interleaving String.
Memory Usage: 13.6 MB, less than 5.07% of Python3 online submissions for Interleaving String.
