交错字符串

标签: 字符串 动态规划

难度: Medium

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

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

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：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 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n = len(s1)
        m = len(s2)
        k = len(s3)
        if n+m != k: return False
        dp = [[False]*(m+1) for _ in range(n+1)]
        dp[0][0] = True
        for i in range(1, n+1):
            if dp[i-1][0] and s1[i-1] == s3[i-1]:
                    dp[i][0] = True
        for j in range(1, m+1):
            if dp[0][j-1] and s2[j-1] == s3[j-1]:
                    dp[0][j] = True
        for i in range(1, n+1):
            for j in range(1, m+1):
                if dp[i][j-1] and s2[j-1] == s3[i+j-1]:
                    dp[i][j] = True
                elif dp[i-1][j] and s1[i-1] == s3[i+j-1]:
                    dp[i][j] = True
        return dp[-1][-1]

Explain

这个题解使用动态规划的思路来解决交错字符串的问题。定义状态 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。状态转移方程为：如果 dp[i][j-1] 为 true 且 s2[j-1] 等于 s3[i+j-1]，或者 dp[i-1][j] 为 true 且 s1[i-1] 等于 s3[i+j-1]，那么 dp[i][j] 为 true。最终结果为 dp[n][m]，其中 n 和 m 分别为 s1 和 s2 的长度。

时间复杂度: O(nm)

空间复杂度: O(nm)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n = len(s1)
        m = len(s2)
        k = len(s3)
        if n+m != k: return False
        
        # 初始化 dp 数组
        dp = [[False]*(m+1) for _ in range(n+1)]
        dp[0][0] = True
        
        # 处理边界情况：s1 为空，s2 与 s3 的前缀匹配
        for i in range(1, n+1):
            if dp[i-1][0] and s1[i-1] == s3[i-1]:
                    dp[i][0] = True
        
        # 处理边界情况：s2 为空，s1 与 s3 的前缀匹配
        for j in range(1, m+1):
            if dp[0][j-1] and s2[j-1] == s3[j-1]:
                    dp[0][j] = True
        
        # 状态转移
        for i in range(1, n+1):
            for j in range(1, m+1):
                if dp[i][j-1] and s2[j-1] == s3[i+j-1]:
                    dp[i][j] = True
                elif dp[i-1][j] and s1[i-1] == s3[i+j-1]:
                    dp[i][j] = True
        
        # 返回最终结果
        return dp[-1][-1]

Explore

在动态规划数组dp中，dp[i][j]为true表示使用s1的前i个字符和s2的前j个字符可以交错组成s3的前i+j个字符。这意味着存在一种方法将s1和s2的这些字符交错排列，使得它们完全匹配s3的前i+j个字符。

在初始化时，dp[i][0]为true表示s1的前i个字符可以单独形成s3的前i个字符，而不使用s2的任何字符。这种情况下，每次添加s1的一个字符到已经形成的序列中，必须确保新添加的字符（s1的第i-1个字符）与s3对应位置的字符（s3的第i-1个字符）相同。如果它们不相同，则无法形成s3的相应前缀，因此dp[i][0]只有在s1的第i-1个字符等于s3的第i-1个字符时才设置为true。

如果s1和s2都为空，那么dp[0][0]的值应该是true。这是因为如果s1和s2都没有字符，那么s3也应该是空字符串才能符合条件（即s3的长度必须是0）。dp[0][0]为true表示空字符串s1和空字符串s2可以组成空字符串s3。

状态转移方程确实考虑了所有可能的字符匹配组合，因为它检查了两种情况：一种是s2的j-1位置的字符可以匹配s3的i+j-1位置的字符，且之前的字符已经通过dp[i][j-1]为true表示可以匹配；另一种是s1的i-1位置的字符可以匹配s3的i+j-1位置的字符，且之前的字符已经通过dp[i-1][j]为true表示可以匹配。这两种情况涵盖了通过添加s1或s2的新字符来匹配s3的所有可能性。