字符串交织问题（三个字符串版本） 题目描述 给定三个字符串s1、s2和s3，判断s3是否能由s1和s2的交织组成。交织是指在不改变s1和s2中字符相对顺序的情况下，将它们交错合并成一个字符串。 例如： 输入：s1 = "aab", s2 = "abc", s3 = "aaabcb" 输出：true 解释：s3可以由s1和s2交织形成：取s1的"aa"，然后s2的"ab"，再s1的"b"，最后s2的"c"，形成"aaabcb" 解题思路 这个问题是经典的两个字符串交织问题的扩展。我们需要检查s3是否能被分解为三个子序列，分别来自s1、s2，且保持各自的字符顺序。 动态规划状态定义 定义dp[ i][ j][ k ]为布尔值，表示s1的前i个字符、s2的前j个字符、s3的前k个字符是否能形成交织。其中： i ∈ [ 0, len(s1)]，j ∈ [ 0, len(s2)]，k ∈ [ 0, len(s3) ] 当k ≠ i + j时，dp[ i][ j][ k ]必然为false，因为总字符数不匹配 状态转移方程 对于每个状态dp[ i][ j][ k ]，考虑最后一个字符可能来自哪个字符串： 如果i > 0且s1[ i-1] == s3[ k-1 ]，那么： dp[ i][ j][ k] = dp[ i][ j][ k] || dp[ i-1][ j][ k-1 ] 如果j > 0且s2[ j-1] == s3[ k-1 ]，那么： dp[ i][ j][ k] = dp[ i][ j][ k] || dp[ i][ j-1][ k-1 ] 边界条件 dp[ 0][ 0][ 0 ] = true（三个空字符串可以交织成空字符串） 算法步骤 获取字符串长度：n1 = len(s1), n2 = len(s2), n3 = len(s3) 如果n1 + n2 ≠ n3，直接返回false 创建三维DP数组dp[ n1+1][ n2+1][ n3+1 ]，初始化为false 设置边界条件：dp[ 0][ 0][ 0 ] = true 三重循环遍历： 第一重：i从0到n1 第二重：j从0到n2 第三重：k从0到n3 如果k ≠ i + j，跳过（字符数不匹配） 检查s1的匹配：如果i > 0且s1[ i-1] == s3[ k-1]，更新dp[ i][ j][ k ] 检查s2的匹配：如果j > 0且s2[ j-1] == s3[ k-1]，更新dp[ i][ j][ k ] 最终返回dp[ n1][ n2][ n3 ] 时间复杂度优化 由于k = i + j，我们可以将三维DP优化为二维： 定义dp[ i][ j ]表示s1的前i个字符和s2的前j个字符能否交织成s3的前i+j个字符 状态转移： dp[ i][ j] = (i > 0 && s1[ i-1] == s3[ i+j-1] && dp[ i-1][ j ]) || (j > 0 && s2[ j-1] == s3[ i+j-1] && dp[ i][ j-1 ]) 示例验证 以s1 = "aab", s2 = "abc", s3 = "aaabcb"为例： dp[ 0][ 0 ] = true dp[ 1][ 0] = true (s1[ 0] == s3[ 0 ]) dp[ 2][ 0] = true (s1[ 1] == s3[ 1 ]) dp[ 2][ 1] = true (s2[ 0] == s3[ 2 ]) dp[ 2][ 2] = true (s2[ 1] == s3[ 3 ]) dp[ 3][ 2] = true (s1[ 2] == s3[ 4 ]) dp[ 3][ 3] = true (s2[ 2] == s3[ 5 ]) 最终dp[ 3][ 3 ] = true，验证成功。