97. Interleaving String
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
First
解题的重要思路是动态规划，根据子问题得出最终的解，从左到右递归判断从i, j中的其中一个等于l。
- 若s1[i]等于s3[l], 则继续判断i+1, j, l+1是否依旧能够满足条件。
- 若s2[j]等于s3[l], 则继续判断i, j+1, l+1是否依旧能够满足条件。
若都不成立，则判断匹配失败，返回False
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
s1_len = len(s1)
s2_len = len(s2)
i, j = 0, 0
def dfs(i, j, l, cache):
if (i, j) in cache:
return cache[(i, j)]
if i == s1_len:
return s2[j:] == s3[l:]
if j == s2_len:
return s1[i:] == s3[l:]
result = False
if s1[i] == s3[l]:
result = result | dfs(i+1, j, l+1, cache)
if s2[j] == s3[l]:
result = result | dfs(i, j+1, l+1, cache)
cache[(i, j)] = result
return result
return dfs(0, 0, 0, {})
s = Solution()
print(s.isInterleave(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
