117.交错字符串

题目

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

交错的意思是：把 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

思路

想象你在玩一个拼字游戏：你有两叠卡片，分别写着s1和s2的字符，你必须按顺序从某一叠中取出一张卡片，拼成s3。

你要判断能否刚好拼完。

我们可以用一张二维表格来记录: 已经用了s1的前i个字符和s2的前j个字符，能否拼出s3的前i+j个字符。

状态定义

设 dp[i][j] 表示：s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。

dp[0][0] = true（空串可以组成空串）
如果 dp[i][j] = true，那么下一步可以：
- 从 s1 取下一个字符（s1[i]），如果它等于 s3[i+j]，则 dp[i+1][j] = true。
- 从 s2 取下一个字符（s2[j]），如果它等于 s3[i+j]，则 dp[i][j+1] = true。反过来，要判断 dp[i][j] 是否为 true，就看它是否可以从上一步转移过来：
如果 dp[i-1][j] == true 且 s1[i-1] == s3[i+j-1]，则 dp[i][j] = true。
或者 dp[i][j-1] == true 且 s2[j-1] == s3[i+j-1]，则 dp[i][j] = true。

转移方程

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

边界条件

dp[0][0] = true
第一行 dp[0][j]：只从 s2 取字符，所以 dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
第一列 dp[i][0]：只从 s1 取字符，所以 dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]

提前剪枝

如果 s1.length + s2.length != s3.length，直接返回 false。

手动模拟（以示例 s1="aabcc", s2="dbbca", s3="aadbbcbcac" 为例）

为了方便，我们用表格展示部分关键步骤（只画少量）： - 初始化 dp[0][0]=true。 - 第一行：dp[0][1]：s2[0]='d' vs s3[0]='a' → 不等 → false。后续第一行都是 false（因为第一个就不匹配）。 - 第一列：dp[1][0]：s1[0]='a' vs s3[0]='a' → 相等且 dp[0][0]=true → true。
dp[2][0]：s1[1]='a' vs s3[1]='a' → true。
dp[3][0]：s1[2]='b' vs s3[2]='d' → false。
所以第一列只有前两个 true。 - 然后按行或按列填充。最终 dp[5][5] 会是 true。

class Solution {
    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
        val m = s1.length
        val n = s2.length
        // 长度必须匹配
        if (m + n != s3.length) return false

        // dp[i][j] 表示 s1 前 i 个和 s2 前 j 个能否交错成 s3 前 i+j 个
        val dp = Array(m + 1) { BooleanArray(n + 1) }

        // 初始化空串
        dp[0][0] = true

        // 初始化第一列：只从 s1 取字符
        for (i in 1..m) {
            dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1]
        }

        // 初始化第一行：只从 s2 取字符
        for (j in 1..n) {
            dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1]
        }

        // 填充剩余表格
        for (i in 1..m) {
            for (j in 1..n) {
                // 从 s1 过来：s1[i-1] 必须等于 s3[i+j-1] 且 dp[i-1][j] 为真
                val fromS1 = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]
                // 从 s2 过来：s2[j-1] 必须等于 s3[i+j-1] 且 dp[i][j-1] 为真
                val fromS2 = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]
                dp[i][j] = fromS1 || fromS2
            }
        }

        return dp[m][n]
    }
}

空间优化版本（一维数组）

因为 dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]，所以可以用一维数组滚动更新：

class Solution {
    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
        val m = s1.length
        val n = s2.length
        if (m + n != s3.length) return false

        // dp[j] 表示当前行（i）的 dp[i][j]
        val dp = BooleanArray(n + 1)

        // 初始化第一行（i=0）
        dp[0] = true
        for (j in 1..n) {
            dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1]
        }

        // 逐行处理
        for (i in 1..m) {
            // 每行第一个元素（j=0）需要单独处理
            dp[0] = dp[0] && s1[i - 1] == s3[i - 1]
            for (j in 1..n) {
                // dp[j] 旧值代表 dp[i-1][j]（上一行），dp[j-1] 代表 dp[i][j-1]（当前行已更新）
                val fromS1 = dp[j] && s1[i - 1] == s3[i + j - 1]
                val fromS2 = dp[j - 1] && s2[j - 1] == s3[i + j - 1]
                dp[j] = fromS1 || fromS2
            }
        }

        return dp[n]
    }
}

复杂度

时间复杂度: O(m × n)需要遍历二维表格的每个格子，每个格子常数操作。
空间复杂度:
- 二维 DP：O(m × n)
- 一维优化：O(n)（n 为 s2 的长度）

下一题

邮箱：charon.chui@gmail.com
Good Luck!