这道题，难在读懂题意，找到状态转移方程。

题目

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

动态规划

示例

示例 1:

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

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

考察知识点

动态规划、回溯算法

核心思想

方法一、动态规划算法

考虑用 s1 和 s2 的某个前缀是否能形成 s3 的一个前缀。
这个方法的前提建立于：判断一个 s3 的前缀（用下标 k 表示），能否用 s1 和 s2 的前缀（下标分别为 i 和 j），仅仅依赖于 s1 前 i 个字符和 s2 前 j 个字符，而与后面的字符无关。
为了实现这个算法， 我们将使用一个 2D 的布尔数组 dp 。dp[i][j] 表示用 s1 的前 (i+1) 和 s2 的前 (j+1) 个字符，总共 (i+j+2) 个字符，是否交错构成 s3 的前缀。为了求出 dp[i][j]，我们需要考虑 2 种情况：

• s1 的第 i 个字符和 s2 的第 j 个字符都不能匹配 s3 的第 k 个字符，其中 k=i+j+1 。这种情况下，s1 和 s2 的前缀无法交错形成 s3 长度为 k+1 的前缀。因此，我们让 dp[i][j] 为 False。
• s1 的第 i 个字符或者 s2 的第 j 个字符可以匹配 s3 的第 k 个字符，其中 k=i+j+1 。假设匹配的字符是 x 且与 s1 的第 i 个字符匹配，我们就需要把 x 放在已经形成的交错字符串的最后一个位置。此时，为了我们必须确保 s1 的前 (i-1) 个字符和 s2 的前 j 个字符能形成 s3 的一个前缀。类似的，如果我们将 s2 的第 j个字符与 s3 的第 k 个字符匹配，我们需要确保 s1 的前 i 个字符和 s2 的前 (j-1) 个字符能形成 s3 的一个前缀，我们就让 dp[i][j] 为 True。

状态转换方程为（下图中i=1，j=0，dp[1][0] = True） \[ dp[i][j] = True\ if\ dp[i][j-1] = True\ and\ S_2(j) = S_3[j+i+1] \]

1.png

或（下图中i=2，j=3，dp[2][3] = True） \[ dp[i][j] = True\ if\ dp[i-1][j] = True\ and\ S_1(i) = S_3[j+i+1] \]

2.png

否则（下图中i=2，j=2，dp[2][2] = False）

\[ dp[i][j] = False \]

3.png

Python版本

方法一动态规划算法实现

from typing import List

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s3) != len(s1) + len(s2):  return False
        dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
        for i in range(0, len(s1) + 1):
            for j in range(0, len(s2) + 1):
                if i == 0 and j == 0:
                    dp[i][j] = True
                elif i == 0:  # 初始化第一行 此时 j >= 1 且 i = 0
                    dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1]
                elif j == 0:  # 初始化第一列 此时 i >= 1 且 j = 0
                    dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1]
                else:  # 开始状态转移部分 i >= 1 且 j >= 1
                    dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        return dp[len(s1)][-1]


Input = ["aabcc", "aabcc"]
Input2 = ["dbbca", "dbbca"]
Input3 = ["aadbbcbcac", "aadbbbaccc"]
Answer = [True, False]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        result = solution.isInterleave(Input[i], Input2[i], Input3[i])
        print(result==Answer[i])

时间复杂度：\(O(m \times n)\) ，计算 dp 数组需要 \(m \times n\) 的时间。
空间复杂度：\(O(m \times n)\)，2 维的 dp 数组需要 \((m+1) \times (n+1)\) 的空间。\(m\) 和 \(n\) 分别是 s1 和 s2 字符串的长度。

参考链接

LeetCode官方题解