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
解释：一种得到 s3 的方法是：
将 s1 分割为 s1 = "aa" + "bc" + "c"，s2 分割为 s2 = "dbbc" + "a" 。
交错得到 "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac" 。

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
解释：无法通过交错 s2 与任何其他字符串来得到 s3 。

示例 3：

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

提示：

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

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

解题思路

这是一个经典的动态规划问题。核心思想是判断字符串s3能否由s1和s2交错组成。

基本思路分析：

首先需要明确，如果s3是s1和s2的交错字符串，那么必须满足 s1.length + s2.length == s3.length，否则直接返回false。

动态规划解法： 定义 dp[i][j] 表示s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符。

状态转移方程：

  • 如果 s1[i-1] == s3[i+j-1] 且 dp[i-1][j] == true，则可以从s1取字符
  • 如果 s2[j-1] == s3[i+j-1] 且 dp[i][j-1] == true，则可以从s2取字符
  • 满足其中任一条件，dp[i][j] 就为true

边界条件：

  • dp[0][0] = true（空字符串的交错）
  • dp[i][0] 表示只使用s1的前i个字符能否组成s3的前i个字符
  • dp[0][j] 表示只使用s2的前j个字符能否组成s3的前j个字符

空间优化： 由于每次状态转移只依赖于上一行和当前行的前一个位置，可以使用一维数组优化空间复杂度到O(min(m,n))。

这种方法能有效处理所有边界情况，包括空字符串的情况。

代码实现

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        
        // 初始化第一行
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j-1] && s2[j-1] == s3[j-1];
        }
        
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1[i-1] == s3[i-1];
            for (int j = 1; j <= n; j++) {
                dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) || 
                        (dp[j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        
        dp = [False] * (n + 1)
        dp[0] = True
        
        # 初始化第一行
        for j in range(1, n + 1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
        
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, n + 1):
                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or \
                        (dp[j-1] and s2[j-1] == s3[i+j-1])
        
        return dp[n]

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        int m = s1.Length, n = s2.Length;
        if (m + n != s3.Length) return false;
        
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        
        // 初始化第一行
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j-1] && s2[j-1] == s3[j-1];
        }
        
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1[i-1] == s3[i-1];
            for (int j = 1; j <= n; j++) {
                dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) || 
                        (dp[j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
        
        return dp[n];
    }
}

var isInterleave = function(s1, s2, s3) {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;
    
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    
    // 初始化第一行
    for (let j = 1; j <= n; j++) {
        dp[j] = dp[j-1] && s2[j-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要填充m×n的动态规划表，其中m和n分别是s1和s2的长度
空间复杂度O(n)使用一维数组优化后的空间复杂度，其中n是s2的长度