字符串交织问题（三个字符串版本） 题目描述 给定三个字符串s1、s2和s3，判断s3是否能由s1和s2的交织形成。交织是指在不改变s1和s2中字符相对顺序的情况下，将它们合并成一个字符串。具体来说，如果s3可以由s1和s2的交织形成，那么s3包含s1的所有字符且顺序不变，同时也包含s2的所有字符且顺序不变。 例如： 输入：s1 = "aab", s2 = "abc", s3 = "aaabbc" 输出：true 解释：s3可以看作是由s1的"aab"和s2的"abc"交织而成（一种交织方式为：a, a, b, a, b, c，但注意这里s1和s2的字符必须保持相对顺序。实际上，s3可以分解为：取s1的前两个字符"aa"，然后取s2的第一个字符"a"，再取s1的最后一个字符"b"，最后取s2的剩余"bc"，形成"aa" + "a" + "b" + "bc" = "aaabbc"，但这样s2的字符顺序被打乱了（'a'应该在'b'和'c'之前，但这里'a'被插入到了中间）。正确的交织必须保持每个字符串自身的顺序。让我们重新检查：s1 = "aab" (a1, a2, b3), s2 = "abc" (a1, b2, c3)。s3 = "aaabbc" 可以表示为：取s1的a1, a2 -> "aa"; 取s2的a1 -> "a" (现在有"aaa"); 取s1的b3 -> "b" (现在有"aaab"); 取s2的b2, c3 -> "bc" (得到"aaabbc")。但是，注意在s2中，a1后面应该是b2，但在我们的取法中，在取了s2的a1之后，我们没有立即取s2的b2，而是先取了s1的b3。这破坏了s2的字符顺序吗？实际上没有，因为交织只要求s2的字符在s3中出现的相对顺序与在s2中相同。也就是说，对于s2中的任意两个字符，如果在s2中x在y前面，那么在s3中x也必须在y前面。同样对于s1。在这个例子中，s2的a1在b2和c3之前，在s3中，a1也确实在b2和c3之前。所以这是有效的交织。 更清晰的例子： s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" -> true 一种交织方式：s1: a a b c c; s2: d b b c a; 交织: a a d b b c b c a c 保持了两者的顺序。 解题过程 我们将使用动态规划来解决这个问题。定义状态和状态转移方程是关键。 状态定义 我们定义dp[ i][ j ]为一个布尔值，表示字符串s1的前i个字符和字符串s2的前j个字符能否交织形成字符串s3的前i+j个字符。 这里，i的范围是0到len(s1)，j的范围是0到len(s2)。当i=0且j=0时，表示用s1的前0个字符和s2的前0个字符交织成s3的前0个字符，这总是true（空字符串可以由两个空字符串交织而成）。 状态转移方程 考虑如何形成s3的前i+j个字符。最后一个字符可能来自s1的第i个字符，也可能来自s2的第j个字符。 如果最后一个字符来自s1，那么需要满足： s1的第i个字符等于s3的第i+j个字符（即s3[ i+j-1] == s1[ i-1 ]，因为字符串索引从0开始）。 并且，s1的前i-1个字符和s2的前j个字符能交织形成s3的前i+j-1个字符（即dp[ i-1][ j ]为true）。 如果最后一个字符来自s2，那么需要满足： s2的第j个字符等于s3的第i+j个字符（即s3[ i+j-1] == s2[ j-1 ]）。 并且，s1的前i个字符和s2的前j-1个字符能交织形成s3的前i+j-1个字符（即dp[ i][ j-1 ]为true）。 因此，状态转移方程为： 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 ]) 注意边界情况： 当i=0时，表示s1没有提供字符，那么s3的前j个字符必须全部由s2的前j个字符按顺序构成。所以dp[ 0][ j] = (s2的前j个字符等于s3的前j个字符)。这可以写成：dp[ 0][ j] = dp[ 0][ j-1] && (s2[ j-1] == s3[ j-1])，并且dp[ 0][ 0 ] = true。 类似地，当j=0时，dp[ i][ 0] = dp[ i-1][ 0] && (s1[ i-1] == s3[ i-1 ]) 初始化 dp[ 0][ 0 ] = true（两个空字符串交织成空字符串）。 第一列（j=0）：dp[ i][ 0] = dp[ i-1][ 0] && (s1[ i-1] == s3[ i-1 ])，对于i从1到len(s1)。 第一行（i=0）：dp[ 0][ j] = dp[ 0][ j-1] && (s2[ j-1] == s3[ j-1 ])，对于j从1到len(s2)。 填表顺序 我们需要计算dp[ i][ j]对于所有i和j的值。由于dp[ i][ j]依赖于dp[ i-1][ j]和dp[ i][ j-1 ]，我们可以按行优先（i从0到len(s1)，对于每个i，j从0到len(s2)）或列优先的顺序填充dp表。 最终结果 dp[ len(s1)][ len(s2) ]的值就是问题的答案，即s1的全部字符和s2的全部字符能否交织成s3的全部字符。注意，只有当len(s1) + len(s2) == len(s3)时才有可能，否则直接返回false。 举例说明 以s1 = "aab", s2 = "abc", s3 = "aaabbc"为例（长度3+3=6，符合）。 初始化dp表，大小为(4)x(4)（i=0..3, j=0..3）。 dp[ 0][ 0 ] = true。 第一行（i=0）： j=1: dp[ 0][ 1] = dp[ 0][ 0] && (s2[ 0]=='a' == s3[ 0 ]=='a') -> true && true -> true。 j=2: dp[ 0][ 2] = dp[ 0][ 1] && (s2[ 1]=='b' == s3[ 1 ]=='a') -> true && false -> false。 j=3: dp[ 0][ 3] = dp[ 0][ 2] && ... -> false (因为dp[ 0][ 2 ]已经是false，后面都是false)。 第一列（j=0）： i=1: dp[ 1][ 0] = dp[ 0][ 0] && (s1[ 0]=='a' == s3[ 0 ]=='a') -> true。 i=2: dp[ 2][ 0] = dp[ 1][ 0] && (s1[ 1]=='a' == s3[ 1 ]=='a') -> true。 i=3: dp[ 3][ 0] = dp[ 2][ 0] && (s1[ 2]=='b' == s3[ 2 ]=='a') -> true && false -> false。 现在填充其他部分： i=1, j=1: 来自s1: dp[ 0][ 1] && (s1[ 0]=='a' == s3[ 1 ]=='a') -> true && true -> true。 来自s2: dp[ 1][ 0] && (s2[ 0]=='a' == s3[ 1 ]=='a') -> true && true -> true。 所以dp[ 1][ 1 ] = true || true -> true。 i=1, j=2: 来自s1: dp[ 0][ 2] && (s1[ 0]=='a' == s3[ 2 ]=='a') -> false && true -> false。 来自s2: dp[ 1][ 1] && (s2[ 1]=='b' == s3[ 2 ]=='a') -> true && false -> false。 所以dp[ 1][ 2 ] = false。 i=1, j=3: 类似，取决于dp[ 0][ 3]和dp[ 1][ 2 ]，都是false，所以false。 i=2, j=1: 来自s1: dp[ 1][ 1] && (s1[ 1]=='a' == s3[ 2 ]=='a') -> true && true -> true。 来自s2: dp[ 2][ 0] && (s2[ 0]=='a' == s3[ 2 ]=='a') -> true && true -> true。 所以dp[ 2][ 1 ] = true。 i=2, j=2: 来自s1: dp[ 1][ 2] && (s1[ 1]=='a' == s3[ 3 ]=='b') -> false && false -> false。 来自s2: dp[ 2][ 1] && (s2[ 1]=='b' == s3[ 3 ]=='b') -> true && true -> true。 所以dp[ 2][ 2 ] = true。 i=2, j=3: 来自s1: dp[ 1][ 3] && (s1[ 1]=='a' == s3[ 4 ]=='b') -> false && false -> false。 来自s2: dp[ 2][ 2] && (s2[ 2]=='c' == s3[ 4 ]=='b') -> true && false -> false。 所以dp[ 2][ 3 ] = false。 i=3, j=1: 来自s1: dp[ 2][ 1] && (s1[ 2]=='b' == s3[ 3 ]=='b') -> true && true -> true。 来自s2: dp[ 3][ 0] && (s2[ 0]=='a' == s3[ 3 ]=='b') -> false && false -> false。 所以dp[ 3][ 1 ] = true。 i=3, j=2: 来自s1: dp[ 2][ 2] && (s1[ 2]=='b' == s3[ 4 ]=='b') -> true && true -> true。 来自s2: dp[ 3][ 1] && (s2[ 1]=='b' == s3[ 4 ]=='b') -> true && true -> true。 所以dp[ 3][ 2 ] = true。 i=3, j=3: 来自s1: dp[ 2][ 3] && (s1[ 2]=='b' == s3[ 5 ]=='c') -> false && false -> false。 来自s2: dp[ 3][ 2] && (s2[ 2]=='c' == s3[ 5 ]=='c') -> true && true -> true。 所以dp[ 3][ 3 ] = true。 最终，dp[ 3][ 3 ] = true，所以s1和s2可以交织成s3。 这个动态规划方法的时间复杂度是O(m n)，空间复杂度也是O(m n)，其中m和n分别是s1和s2的长度。我们可以通过滚动数组优化空间复杂度到O(n)。