题解 | #交错编号#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 定义一个三维数组 dp，其中 dp[i][j][k] 表示 s1 中前 i 个字符和 s2 中前 j 个字符交错组成 s3 中前 k 个字符的方案是否存在

对于第 k 个字符，它有两种来源：

2. 如果它来自 s1 的第 i 个字符，那么它可能是与 s1 中前 i−1 个字符和 s2 中前 j 个字符交错得到的，需要满足 s1i−1​=s3k−1​；
3. 如果它来自 s2 的第 j 个字符，那么它可能是与 s1 中前 i 个字符和 s2 中前 j−1 个字符交错得到的，需要满足 s2j−1​=s3k−1​。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s1 string字符串
# @param s2 string字符串
# @param s3 string字符串
# @return bool布尔型
#
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)
        if m + n != l:
            return False
        dp = [[[False] * (l + 1) for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0][0] = True
        for j in range(1, n + 1):
            dp[0][j][j] = dp[0][j - 1][j - 1] and s2[j - 1] == s3[j - 1]
        for i in range(1, m + 1):
            dp[i][0][i] = dp[i - 1][0][i - 1] and s1[i - 1] == s3[i - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                k = i + j
                if s1[i - 1] == s3[k - 1]:
                    dp[i][j][k] = dp[i - 1][j][k - 1]
                if s2[j - 1] == s3[k - 1]:
                    dp[i][j][k] |= dp[i][j - 1][k - 1]
        return dp[m][n][l]