题解 | #交织子序列#

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

1. 定义一个二维数组dp,其中dp[i][j]表示字符串 s 的前i个字符串s的前j个字符是否能够交织成字符串t的前i+j个字符的子序列。
2. 对于字符串s和x中的每个字符,我们都有两种选择:
3. 将它加入当前组成的子序列中;
4. 将它不加入当前组成的子序列中;
5. 得出状态转移方程

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param x string字符串
# @param t string字符串
# @return bool布尔型
#
class Solution:
    def isInterleave(self, s: str, x: str, t: str) -> bool:
        m, n = len(s), len(x)
        if m + n != len(t):
            return False
        # dp[i][j] 表示 s 的前 i 个字符和 x 的前 j 个字符能否构成 t 的前 i+j 个字符的子序列
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s[i - 1] == t[i - 1]
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and x[j - 1] == t[j - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[i - 1][j] and s[i - 1] == t[i + j - 1]) or (
                    dp[i][j - 1] and x[j - 1] == t[i + j - 1]
                )
        return dp[m][n]