- 分类：DP
- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2)
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
代码：
class Solution:
def isInterleave(self, s1: 'str', s2: 'str', s3: 'str') -> 'bool':
#判断边界条件
if s1==None and s2==None and s3==None:
return True
if s1==None or s2==None or s3==None:
return False
if len(s1)+len(s2)!=len(s3):
return False
dp=[[False for i in range(len(s2)+1)] for i in range(len(s1)+1)]
dp[0][0]=True
for i in range(1,len(s3)+1):
lens1=0
while lens1<=i and lens1<=len(s1):
lens2=i-lens1
if lens2>len(s2):
lens1=i-len(s2)
continue
if (lens2>0 and s3[i-1]==s2[lens2-1] and dp[lens1][lens2-1]) or \
(lens1>0 and s3[i-1]==s1[lens1-1] and dp[lens1-1][lens2]):
dp[lens1][lens2]=True
lens1+=1
return dp[-1][-1]
讨论：
1.计数题和True/False的题目都要考虑用DP做
2.DP有四个要素
- state状态，这里是true or false
- init初始条件
- function，这个最重要
- result给出的结果
- 这里的转移方程是当s3最后一个字符等于s2最后一个字符的时候且dp[lens1][lens2-1]==True的时候，dp[lens1][lens2]==True
4.在lens2>len(s2)的时候，为了加快进度，lens1=i-len(s2)可以加个速
5.但好像DP本身就不快？？？
