交错字符串

难度: Medium

给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。

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

s = s₁ + s₂ + ... + s_n
t = t₁ + t₂ + ... + t_m
|n - m| <= 1
交织是 s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ... 或者 t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

提示：a + b 意味着字符串 a 和 b 连接。

示例 1：

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

示例 2：

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

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

注意：本题与主站 97 题相同： https://leetcode-cn.com/problems/interleaving-string/

Submission

运行时间: 28 ms

内存: 16.1 MB

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

        dp = [[False for _ in range(n2+1)] for _ in range(n1+1)]
        # dp[i][j]表示s1[:i]与s2[:j]是否能组成s3[:i+j]

        dp[0][0] = True
        for i in range(1,n1+1):
            if s3[i-1] == s1[i-1]:
                dp[i][0] = True
            else:
                break

        for j in range(1, n2+1):
            if s2[j-1] == s3[j-1]:
                dp[0][j] = True
            else:
                break
        
        for i in range(1,n1+1):
            for j in range(1, n2+1):
                dp[i][j] = dp[i-1][j] and (s1[i-1] == s3[i+j-1])
                dp[i][j] = dp[i][j] or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        return dp[-1][-1]

Explain

此题解采用动态规划的方法来解决交错字符串问题。首先，我们定义一个二维的布尔数组dp，其中dp[i][j]表示字符串s1的前i个字符和s2的前j个字符是否能交错组成s3的前i+j个字符。初始化dp[0][0]为True，表示空字符串可以组成空字符串。然后，初始化第一行和第一列，分别表示只使用s1或s2时的情况。对于矩阵中剩余的元素，通过检查s1的当前字符是否与s3的对应字符匹配来更新dp[i][j]，如果匹配，则参考左侧的dp值（即不包括当前字符的s1和s2的组合）。同理，检查s2的当前字符是否匹配，并参考上方的dp值。最终，dp[n1][n2]给出了整个字符串的匹配结果。

时间复杂度: O(n1 * n2)

空间复杂度: O(n1 * n2)

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

        dp = [[False for _ in range(n2+1)] for _ in range(n1+1)]
        # dp[i][j]表示s1[:i]与s2[:j]是否能组成s3[:i+j]

        dp[0][0] = True
        for i in range(1,n1+1):
            if s3[i-1] == s1[i-1]:
                dp[i][0] = True
            else:
                break

        for j in range(1, n2+1):
            if s2[j-1] == s3[j-1]:
                dp[0][j] = True
            else:
                break

        for i in range(1,n1+1):
            for j in range(1, n2+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[-1][-1]

Explore

在初始化dp数组时，dp[i][0]为True表示仅使用s1的前i个字符就能组成s3的前i个字符。如果在某个位置i，s3的第i个字符与s1的第i个字符不匹配，则意味着s1的前i个字符无法单独组成s3的前i个字符，因此在这种情况下将dp[i][0]设置为False。初始化过程中的这种匹配检查是为了确定在仅使用s1字符时，各个阶段是否能够满足交错组成s3的条件。

这个更新规则确保了只有当当前字符匹配时，我们才考虑将其加入到交错字符串中。这里dp[i][j]的更新依赖于两个条件：1) dp[i-1][j]和s1[i-1]与s3[i+j-1]的匹配，表示如果不包括s1的当前字符，之前的字符已经可以组成s3的前i+j-1个字符；2) dp[i][j-1]和s2[j-1]与s3[i+j-1]的匹配，表示如果不包括s2的当前字符，之前的字符已经可以组成s3的前i+j-1个字符。这种方法确保了只有在字符完全匹配的情况下，我们才认为s1的前i个字符和s2的前j个字符能够交错组成s3的前i+j个字符。

在这个算法中，如果s1和s2的长度之和不等于s3的长度，那么它们无法组成s3，因为字符总数不匹配，直接返回False。除此之外，如果s1和s2为空字符串且s3也为空，那么应该返回True，但这种情况已经在dp[0][0]的初始化中处理了。因此，不等长的直接判断是必要的，且在这种情况下提前返回结果是合理的，其他情况则需要通过动态规划的过程来确定结果。