97. 交错字符串

题目：

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

30min ,dp边界整的够呛，不过还好做出来了。

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1)+len(s2)!=len(s3):return False
        if not s1:return s2==s3
        if not s2:return s1==s3
        if not s3:return True
        s1="@"+s1
        s3="@"+s3
        n1,n2,n3=len(s1),len(s2),len(s3)
        dp=[[False]*(n1) for _ in range(n3)]
        dp[0][0]=True
        for i in range(1,n3):
            for j in range(min(n1,i+1)):
                k= i-j-1
                if s3[i]==s1[j]:
                    dp[i][j]=dp[i][j] or dp[i-1][j-1]
                if 0<=k<n2 and s3[i]==s2[k]:
                    dp[i][j]=dp[i][j] or dp[i-1][j]
        return dp[-1][-1]

要点：

1. 边界条件 在1串和3串前面+个特殊符号就好处理多了

2. j和k的范围需要注意。

3. 更新的时候用or更新

不然一个好好的True 就变成了False了。

其他：

代码报错：无