题目

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
提示：a + b 意味着字符串 a 和 b 连接。

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

解法一：DFS 超时
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def cal(index_s1, index_s2, index_s3):
            if index_s3 == len(s3):
                if index_s1 == len(s1) and index_s2 == len(s2):
                    return True
                else:
                    return False

            if index_s1 <= len(s1) - 1:
                if s1[index_s1] == s3[index_s3]:
                    index_s1 += 1
                    index_s3 += 1
                    if cal(index_s1, index_s2, index_s3):
                        return True
                    else:
                        index_s1 -= 1
                        index_s3 -= 1

            if index_s2 <= len(s2) - 1:
                if s2[index_s2] == s3[index_s3]:
                    index_s2 += 1
                    index_s3 += 1
                    return cal(index_s1, index_s2, index_s3)
            return False

        return cal(0, 0, 0)
解法二：动态规划
关键是找到状态转移方程
f(i,j)定义为s1的前i个和s2的前j个，P表示当前s3的第p个元素
首先必须满足i+j=p
f(i,j)=f(i-1,j) and s1(i-1) = s3(p) s1最后一个元素和s3第p个元素相等
f(i,j)=f(i,j-1) and s1(j-1) = s3(p) s1最后一个元素和s3第p个元素相等
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        i = len(s1)
        j = len(s2)
        m = len(s3)
        if i+j != m:
            return False
        array = [[ False for _ in range(j+1) ] for _ in range(i+1) ]
        array[0][0] = True
        for i1 in range(i+1):
            for j1 in range(j+1):
                p = i1 + j1 - 1
                if i1 > 0:
                    array[i1][j1] = array[i1][j1] or (array[i1-1][j1] and s1[i1-1] == s3[p])
                if j1 > 0:
                    array[i1][j1] = array[i1][j1] or (array[i1][j1-1] and s2[j1-1] == s3[p])

        return array[i][j]