带限制的字符串交织问题 题目描述 给定三个字符串 s1 、 s2 和 s3 ，判断 s3 是否能由 s1 和 s2 交错组成。交错要求：保持 s1 和 s2 中字符的相对顺序不变。例如： s1 = "aab" , s2 = "abc" , s3 = "aaabcb" → 返回 true （交错方式： s1 取前两个 "aa"， s2 取第一个 "a"， s1 取最后一个 "b"， s2 取剩余 "bc"）。 s1 = "aab" , s2 = "abc" , s3 = "aaabbc" → 返回 false （无法保持相对顺序）。 解题思路 问题分析 若 s3 的长度不等于 s1 与 s2 长度之和，直接返回 false 。 核心挑战：在合并过程中，必须保持 s1 和 s2 各自的字符顺序。 动态规划定义 定义 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能交错组成 s3 的前 i+j 个字符。 状态转移方程 若 s1[i-1] == s3[i+j-1] ，则 dp[i][j] 取决于 dp[i-1][j] （即当前字符匹配 s1 的前一状态）。 若 s2[j-1] == s3[i+j-1] ，则 dp[i][j] 取决于 dp[i][j-1] （即当前字符匹配 s2 的前一状态）。 综合： \[ 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 的前 j 个字符与 s3 的前 j 个字符完全匹配时为 true 。 第一列 dp[i][0] ：仅当 s1 的前 i 个字符与 s3 的前 i 个字符完全匹配时为 true 。 计算顺序 按 i 从 0 到 len(s1) ， j 从 0 到 len(s2) 顺序填表。 示例推导 以 s1 = "aab" , s2 = "abc" , s3 = "aaabcb" 为例： 初始化 dp[0][0] = true 。 第一行： dp[0][1] 需判断 s2[0] == s3[0] （'a' vs 'a'）→ true ；同理逐列填充。 计算 dp[1][1] ： 匹配 s1 ： dp[0][1] && s1[0] == s3[1] （ true && 'a' == 'a' ）→ true 。 匹配 s2 ： dp[1][0] && s2[0] == s3[1] （ true && 'a' == 'a' ）→ true 。 最终 dp[1][1] = true 。 逐步填表至 dp[3][3] ，检查最终结果。 复杂度分析 时间复杂度：O(m·n)，其中 m 和 n 分别为 s1 和 s2 的长度。 空间复杂度：可优化至 O(min(m, n))，仅存储一行或一列的状态。 关键点 交错组成需严格保持原字符串顺序，动态规划通过状态转移模拟字符匹配的两种来源。 边界条件需单独处理，避免越界错误。