leetcode题解97：交错字符串

描述

分析

比如字符串\(s_1=a_1a_2..a_l\)，\(s_2=b_1b_2..b_m\)，\(s_3=c_1c_2...c_{l+m}\)，要判断\(s_3\)是否由\(s_1,s_2\)交错生成，还是以化成小问题为目标，首先当\(a_l\)与\(b_m\)都不等于\(c_{l+m}\)时，显然不可能是\(s_1,s_2\)生成的；

从而先假设\(a_l = c_{l+m}\)，那么不就是看\(a_1...a_{l-1}\)与\(s_2\)是否可以生成\(c_1...c_{l+m-1}\)吗？这就化成了相似的小问题了。

\(b_m = c_{l+m}\)时，同理可得。所以该题可以用动态规划解决。记dp[i][j]表示\(a_1...a_i\)与\(b_1...b_j\)是否可生成\(c_1...c_{i+j}\)，那么转移方程就是

1	dp[i][j] = (dp[i-1][j] & s1[i]==s3[i+j]) \| (dp[i][j-1] & s2[j]==s3[i+j])

最后注意边界条件即可。

代码

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if (len(s1) + len(s2)) != len(s3):
            return False

        dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
        dp[0][0] = True
        for i in range(0, len(s1)+1):
            for j in range(0, len(s2)+1):
                if i > 0:
                    dp[i][j] = (s1[i-1] == s3[i+j-1]) and dp[i-1][j]
                if j > 0:
                    dp[i][j] |= (s2[j-1] == s3[i+j-1] and dp[i][j-1])
        return dp[len(s1)][len(s2)]