区间动态规划例题：字符串交织问题（三个字符串版本）

字数 1852 2025-11-07 12:33:00

区间动态规划例题：字符串交织问题（三个字符串版本）

题目描述

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

s1 = "aab", s2 = "abc", s3 = "aaabcb" → 返回 true（因为 s3 可拆分为 s1 的 "a"+"a"+"b" 和 s2 的 "a"+"b"+"c" 交错组合）。
s1 = "aab", s2 = "abc", s3 = "aaabbc" → 返回 false（因为 s3 中 s2 的字符 'c' 出现在 'b' 之前，但 s2 中 'b' 在 'c' 前面，顺序被破坏）。

解题思路

这是一个经典的区间动态规划问题（实际是二维DP，但本质是区间填充思想）。我们需要检查 s3 的前 i+j 个字符是否能由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成。

步骤1：定义状态

设 dp[i][j] 表示：

s1 的前 i 个字符（即 s1[0:i]）
和 s2 的前 j 个字符（即 s2[0:j]）
能否交错组成 s3 的前 i+j 个字符（即 s3[0:i+j]）。

步骤2：状态转移方程

考虑最后一个字符的来源：

如果 s3 的第 i+j-1 个字符等于 s1 的第 i-1 个字符，并且 dp[i-1][j] 为 true，则说明当前字符可以来自 s1。
如果 s3 的第 i+j-1 个字符等于 s2 的第 j-1 个字符，并且 dp[i][j-1] 为 true，则说明当前字符可以来自 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])

步骤3：边界条件

dp[0][0] = true（空字符串可以组成空字符串）。
第一列 dp[i][0]：表示只使用 s1 的前 i 个字符匹配 s3 的前 i 个字符，需满足 s1[0:i] == s3[0:i]。
第一行 dp[0][j]：类似，只使用 s2 的前 j 个字符匹配 s3 的前 j 个字符。

步骤4：计算顺序

从小到大遍历 i 从 0 到 len(s1)，j 从 0 到 len(s2)。

详细示例

以 s1 = "aab", s2 = "abc", s3 = "aaabcb" 为例：

初始化：
- dp[0][0] = true。
- dp[i][0]：检查 s1 前缀是否匹配 s3 前缀。
  - i=1: s1[0]='a', s3[0]='a' → dp[1][0]=true。
  - i=2: s1[1]='a', s3[1]='a' → dp[2][0]=true。
  - i=3: s1[2]='b', s3[2]='a' → dp[3][0]=false。
- dp[0][j]：类似检查 s2 前缀。
填充表格（部分关键值）：
- dp[1][1]：
  - 最后一个字符 s3[1]='a'，可来自 s1[0]='a'（需 dp[0][1] 为 true）或 s2[0]='a'（需 dp[1][0] 为 true）。
  - dp[1][0]=true，且 s2[0]=='a' → dp[1][1]=true。
- 最终 dp[3][3]：
  - 最后一个字符 s3[5]='b'，可来自 s1[2]='b'（需 dp[2][3] 为 true）或 s2[2]='c'（不匹配）。
  - 检查 dp[2][3]：
    - 它依赖 dp[1][3] 和 dp[2][2] 的推导，最终会传递到 dp[3][3]=true。
结果：dp[len(s1)][len(s2)] 即为答案。

复杂度分析

时间复杂度：O(m*n)，其中 m 和 n 是 s1 和 s2 的长度。
空间复杂度：可优化到 O(min(m,n))，但基础版本为 O(m*n)。

这个方法通过动态规划逐字符匹配，确保了 s1 和 s2 的字符顺序在 s3 中不被破坏。

区间动态规划例题：字符串交织问题（三个字符串版本）题目描述给定三个字符串 s1 、 s2 和 s3 ，判断 s3 是否能由 s1 和 s2 的字符交错形成。交错形成是指：保持 s1 和 s2 中字符的相对顺序不变，将它们穿插合并成一个字符串。示例： s1 = "aab" , s2 = "abc" , s3 = "aaabcb" → 返回 true （因为 s3 可拆分为 s1 的 "a"+"a"+"b" 和 s2 的 "a"+"b"+"c" 交错组合）。 s1 = "aab" , s2 = "abc" , s3 = "aaabbc" → 返回 false （因为 s3 中 s2 的字符 'c' 出现在 'b' 之前，但 s2 中 'b' 在 'c' 前面，顺序被破坏）。解题思路这是一个经典的区间动态规划问题（实际是二维DP，但本质是区间填充思想）。我们需要检查 s3 的前 i+j 个字符是否能由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成。步骤1：定义状态设 dp[i][j] 表示： s1 的前 i 个字符（即 s1[0:i] ）和 s2 的前 j 个字符（即 s2[0:j] ）能否交错组成 s3 的前 i+j 个字符（即 s3[0:i+j] ）。步骤2：状态转移方程考虑最后一个字符的来源：如果 s3 的第 i+j-1 个字符等于 s1 的第 i-1 个字符，并且 dp[i-1][j] 为 true ，则说明当前字符可以来自 s1 。如果 s3 的第 i+j-1 个字符等于 s2 的第 j-1 个字符，并且 dp[i][j-1] 为 true ，则说明当前字符可以来自 s2 。因此：步骤3：边界条件 dp[0][0] = true （空字符串可以组成空字符串）。第一列 dp[i][0] ：表示只使用 s1 的前 i 个字符匹配 s3 的前 i 个字符，需满足 s1[0:i] == s3[0:i] 。第一行 dp[0][j] ：类似，只使用 s2 的前 j 个字符匹配 s3 的前 j 个字符。步骤4：计算顺序从小到大遍历 i 从 0 到 len(s1) ， j 从 0 到 len(s2) 。详细示例以 s1 = "aab" , s2 = "abc" , s3 = "aaabcb" 为例：初始化： dp[0][0] = true 。 dp[i][0] ：检查 s1 前缀是否匹配 s3 前缀。 i=1 : s1[0]='a' , s3[0]='a' → dp[1][0]=true 。 i=2 : s1[1]='a' , s3[1]='a' → dp[2][0]=true 。 i=3 : s1[2]='b' , s3[2]='a' → dp[3][0]=false 。 dp[0][j] ：类似检查 s2 前缀。填充表格（部分关键值）： dp[1][1] ：最后一个字符 s3[1]='a' ，可来自 s1[0]='a' （需 dp[0][1] 为 true）或 s2[0]='a' （需 dp[1][0] 为 true）。 dp[1][0]=true ，且 s2[0]=='a' → dp[1][1]=true 。最终 dp[3][3] ：最后一个字符 s3[5]='b' ，可来自 s1[2]='b' （需 dp[2][3] 为 true）或 s2[2]='c' （不匹配）。检查 dp[2][3] ：它依赖 dp[1][3] 和 dp[2][2] 的推导，最终会传递到 dp[3][3]=true 。结果： dp[len(s1)][len(s2)] 即为答案。复杂度分析时间复杂度：O(m* n)，其中 m 和 n 是 s1 和 s2 的长度。空间复杂度：可优化到 O(min(m,n))，但基础版本为 O(m* n)。这个方法通过动态规划逐字符匹配，确保了 s1 和 s2 的字符顺序在 s3 中不被破坏。