区间动态规划例题：字符串交织问题（进阶版）

题目描述
给定三个字符串 s1、s2 和 s3，判断 s3 是否能由 s1 和 s2 的字符交错形成。交错形成是指：保持 s1 和 s2 的字符相对顺序不变，将它们穿插合并成 s3。
例如：

• 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
• 输出：true
• 解释：s3 可由 s1 和 s2 交替取字符构成（如：s1取"aa"、s2取"dbbc"、s1取"bc"、s2取"a"、s1取"c"）。

约束条件

• 0 ≤ |s1|, |s2|, |s3| ≤ 200
• 字符串仅包含小写字母
• 需保证 |s1| + |s2| = |s3|，否则直接返回 false

解题思路

1. 问题分析

   • 若直接尝试所有交错方式会是指数级复杂度，需用动态规划优化。
   • 关键观察：s3 的前 i+j 个字符是否由 s1 的前 i 个字符和 s2 的前 j 个字符交织而成，取决于两个子问题的结果。

2. 状态定义

   • 定义 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交织成 s3 的前 i+j 个字符。
   • 注意：i 和 j 分别表示已使用的字符数（从0开始）。

3. 状态转移方程

   • 初始状态：dp[0][0] = true（空字符串可以交织成空字符串）。
   • 对于 dp[i][j]：
     • 若 i > 0 且 s1[i-1] == s3[i+j-1]，则检查 dp[i-1][j]（即当前字符来自 s1）。
     • 若 j > 0 且 s2[j-1] == s3[i+j-1]，则检查 dp[i][j-1]（即当前字符来自 s2）。
     • 转移方程：

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

4. 边界处理

   • 当 i=0 时，只能从 s2 取字符：dp[0][j] = (s2[j-1] == s3[j-1]) && dp[0][j-1]。
   • 当 j=0 时，只能从 s1 取字符：dp[i][0] = (s1[i-1] == s3[i-1]) && dp[i-1][0]。

逐步计算示例
以 s1 = "aab", s2 = "dbbc", s3 = "aadbbbc" 为例（简化版，实际需匹配长度）：

1. 初始化 dp[0][0] = true。
2. 第一行（仅用 s2）：
   • dp[0][1]：s2[0]='d' vs s3[0]='a' → false。
   • 后续直接为 false，无需计算。
3. 第一列（仅用 s1）：
   • dp[1][0]：s1[0]='a' == s3[0]='a' 且 dp[0][0]=true → true。
   • dp[2][0]：s1[1]='a' == s3[1]='a' 且 dp[1][0]=true → true。
   • dp[3][0]：s1[2]='b' != s3[2]='d' → false。
4. 计算 dp[1][1]：
   • 来自 s1：s1[0]='a' != s3[1]='a'？注意 s3 索引为 i+j-1=1，s3[1]='a'，但 s1[0] 已用于 dp[0][1]？需重新核对：
     实际应逐步填充表格，检查每个位置是否可能由上方或左方转移而来。

复杂度优化

• 时间复杂度：O(mn)，其中 m、n 为 s1、s2 长度。
• 空间复杂度：可优化至 O(min(m,n)) 使用一维数组（滚动数组）。

关键点

• 状态定义中 i 和 j 表示字符数，访问字符时需减1。
• 需先检查长度是否匹配，否则直接返回 false。
• 交错需保持原字符串顺序，因此只能从 s1 或 s2 的头部依次取字符。