[DP]97. Interleaving String

• 分类：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给出的结果

3. 这里的转移方程是当s3最后一个字符等于s2最后一个字符的时候且dp[lens1][lens2-1]==True的时候，dp[lens1][lens2]==True
   4.在lens2>len(s2)的时候，为了加快进度，lens1=i-len(s2)可以加个速
   5.但好像DP本身就不快？？？