97. Interleaving String

暴力递归

# V1 暴力 class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: size1, size2, size3 = len(s1), len(s2), len(s3) if size1 + size2 != size3: # 当s1和s2的长度加起来不等于s3的长度,肯定无法交错组成 return False def ishelp(index1, index2, index3): # 用于判断s3[index3:]是否能够由s1[index1:]和s2[index2:]交错组成。 # print(index1, index2) if index1 == size1: return s2[index2:] == s3[index3:] if index2 == size2: return s1[index1:] == s3[index3:] # 若s3[index3] == s1[index1] 且 s3[index3+1:]是否能够由s1[index1+1:]和s2[index2:]交错组成则返回True if (s3[index3] == s1[index1] and ishelp(index1+1, index2, index3+1)): return True # 若s3[index3] == s2[index2] 且 s3[index3+1:]是否能够由s1[index1:]和s2[index2+1:]交错组成则返回True if (s3[index3] == s2[index2] and ishelp(index1, index2+1, index3+1)): return True return False return ishelp(0, 0, 0)

带备忘录的递归

# V2 带备忘录的递归 Runtime: 28 ms, faster than 92.50%; Memory Usage: 14.5 MB, less than 100.00% class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: size1, size2, size3 = len(s1), len(s2), len(s3) if size1 + size2 != size3:# 当s1和s2的长度加起来不等于s3的长度,肯定无法交错组成 return False memo = [[-1]*(size2+1) for _ in range(size1+1)] def ishelp(index1, index2, index3): # 用于判断s3[index3:]是否能够由s1[index1:]和s2[index2:]交错组成。 if memo[index1][index2] != -1: # 若(index1, index2)的组合已经计算过，则可直接返回记录的结果 return memo[index1][index2] == 1 if index1 == size1: return s2[index2:] == s3[index3:] if index2 == size2: return s1[index1:] == s3[index3:] # 若s3[index3] == s1[index1] 且 s3[index3+1:]是否能够由s1[index1+1:]和s2[index2:]交错组成则返回True, 并记录(index1, index2)组合的结果 # 若s3[index3] == s2[index2] 且 s3[index3+1:]是否能够由s1[index1:]和s2[index2+1:]交错组成则返回True, 并记录(index1, index2)组合的结果 if (s3[index3] == s1[index1] and ishelp(index1+1, index2, index3+1)) \ or (s3[index3] == s2[index2] and ishelp(index1, index2+1, index3+1)): memo[index1][index2] = 1 return True # 记录(index1, index2)组合的结果 memo[index1][index2] = 0 return False return ishelp(0, 0, 0)

动态规划

# 动态规划 class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: size1, size2, size3 = len(s1), len(s2), len(s3) if size1 + size2 != size3: # 当s1和s2的长度加起来不等于s3的长度,肯定无法交错组成 return False dp = [[False]*(size2+1) for _ in range(size1+1)] # dp[i][j]表示s3[i+j-1]是否能够由s1[:i]和s2[:j]交错组合而成 # 当s1[i - 1] == s3[i+j-1]且dp[i-1][j]为真 或 当s2[j - 1] == s3[i+j-1]且dp[i][j-1]为真时, dp[i][j]为真；否则为假 for i in range(size1+1): for j in range(size2+1): if i == 0 and j == 0: dp[i][j] = True elif i == 0: dp[i][j] = s2[j - 1] == s3[i + j - 1] and dp[i][j - 1] elif j == 0: dp[i][j] = s1[i - 1] == s3[i + j - 1] and dp[i - 1][j] else: dp[i][j] = (s1[i - 1] == s3[i+j-1] and dp[i-1][j]) or (s2[j - 1] == s3[i+j-1] and dp[i][j-1]) return dp[size1][size2]