LeetCode LCR 096. 交错字符串

Categories:

题目描述
思路分析
1. 解法一：二维动态规划（推荐）
2. 解法二：一维动态规划（空间优化）
相似题目

题目描述

✅ LCR 096. 交错字符串

思路分析

解法一：二维动态规划（推荐）

核心思路：

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

初始状态：dp[0][0] = true，空串与空串交错组成空串。

状态转移：dp[i][j] 为 true 当且仅当以下两个条件之一成立：

s1[i-1] == s3[i+j-1] 且 dp[i-1][j] == true（使用 s1 的第 i 个字符）

s2[j-1] == s3[i+j-1] 且 dp[i][j-1] == true（使用 s2 的第 j 个字符）

边界条件：若 len(s1) + len(s2) != len(s3)，直接返回 false。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别是 s1 和 s2 的长度，需要遍历整个二维 dp 数组。

空间复杂度：O(m × n)，使用了大小为 (m+1) × (n+1) 的二维数组存储状态。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        // 长度不匹配直接返回 false
        if (m + n != s3.length()) {
            return false;
        }

        // dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符能否交错组成 s3 前 i+j 个字符
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        // 初始化第一列：只使用 s1 的字符
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // 初始化第一行：只使用 s2 的字符
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 使用 s1 的第 i 个字符，或使用 s2 的第 j 个字符
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        return dp[m][n];
    }
}

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)
	// 长度不匹配直接返回 false
	if m+n != len(s3) {
		return false
	}

	// dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符能否交错组成 s3 前 i+j 个字符
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true

	// 初始化第一列：只使用 s1 的字符
	for i := 1; i <= m; i++ {
		dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
	}

	// 初始化第一行：只使用 s2 的字符
	for j := 1; j <= n; j++ {
		dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			// 使用 s1 的第 i 个字符，或使用 s2 的第 j 个字符
			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])
		}
	}

	return dp[m][n]
}

解法二：一维动态规划（空间优化）

核心思路：

观察二维 dp 的转移方程，dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]，可以将二维数组压缩为一维。

用 dp[j] 滚动表示当前行的状态，遍历 i 时原地更新。

dp[j] 在更新前代表 dp[i-1][j]（上一行），dp[j-1] 刚被更新过，代表 dp[i][j-1]（当前行左侧）。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别是 s1 和 s2 的长度。

空间复杂度：O(n)，只使用了长度为 n+1 的一维数组。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        // 长度不匹配直接返回 false
        if (m + n != s3.length()) {
            return false;
        }

        // 压缩为一维 dp，dp[j] 表示当前 s1 前 i 个与 s2 前 j 个能否交错组成 s3 前 i+j 个
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // 初始化第一行：只使用 s2 的字符
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        for (int i = 1; i <= m; i++) {
            // 更新 dp[0]：只使用 s1 的字符
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                // dp[j] 此时仍为上一行的值，即 dp[i-1][j]
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        return dp[n];
    }
}

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)
	// 长度不匹配直接返回 false
	if m+n != len(s3) {
		return false
	}

	// 压缩为一维 dp，dp[j] 表示当前 s1 前 i 个与 s2 前 j 个能否交错组成 s3 前 i+j 个
	dp := make([]bool, n+1)
	dp[0] = true

	// 初始化第一行：只使用 s2 的字符
	for j := 1; j <= n; j++ {
		dp[j] = dp[j-1] && s2[j-1] == s3[j-1]
	}

	for i := 1; i <= m; i++ {
		// 更新 dp[0]：只使用 s1 的字符
		dp[0] = dp[0] && s1[i-1] == s3[i-1]
		for j := 1; j <= n; j++ {
			// dp[j] 此时仍为上一行的值，即 dp[i-1][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]
}

相似题目

题目	难度	考察点
44. 通配符匹配	困难	动态规划、字符串
10. 正则表达式匹配	困难	动态规划、字符串
72. 编辑距离	中等	动态规划、二维 DP
1143. 最长公共子序列	中等	动态规划、字符串
115. 不同的子序列	困难	动态规划、子序列
1035. 不相交的线	中等	动态规划、等价 LCS
面试题 08.03. 魔术索引	简单	动态规划、数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/47313550