京公网安备11010502063487号给定三个字符串 s1、s2、s3，判断 s3 是否由 s1 和 s2 交错组成：把 s1 和 s2 各自切成若干段，然后把这些段交替地排列，得到 s3；两个字符串内部的字符顺序都不能变。例如 s1 = aabcc、s2 = dbbca 可以交错成 aadbbcbcac。每一步取 s3 的下一个字符，它可能来自 s1，也可能来自 s2，如果两边的下一个字符恰好相同，就要试两种可能，这正是动态规划的场景。dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错成 s3 的前 i + j 个字符：最后一个字符要么来自 s1（需要 s1[i-1] == s3[i+j-1] 且 dp[i-1][j] 为真），要么来自 s2。本文用真实数据展示"两边都匹配时固定选 s1"的贪心为什么不行，展示朴素递归的调用次数，给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。基准解是朴素递归：从前往后，每一步看 s3 的下一个字符，能匹配 s1 就走 s1，能匹配 s2 就走 s2，两种都试，与动态规划是同一个定义的两种实现方式。一共 15 组用例，覆盖：官方两个示例、三个都是空串、有一个是空串、长度不匹配的、s1 和 s2 相同的字符导致要回溯的：
输入 ["aabcc","dbbca","aadbbcbcac"] 输出 true 输入 ["aabcc","dbbca","aadbbbaccc"] 输出 false 输入 ["","",""] 输出 true 输入 ["a","","a"] 输出 true 输入 ["","b","b"] 输出 true 输入 ["a","b","ab"] 输出 true
一个直觉的写法是：逐个看 s3 的字符，如果 s1 的下一个字符匹配就用 s1 的，否则用 s2 的，一次过扫描，不回溯。但当两边的下一个字符都能匹配时，选哪一边会影响后面能否成功，一旦选错就再也回不去了。下面是这种贪心与 solve 的真实结果：
# 两个串都能匹配时固定优先用 s1（贪心，不回溯）的写法 s1='aabcc', s2='dbbca', s3='aadbbcbcac': 贪心 -> False solve -> True s1='aa', s2='ab', s3='abaa': 贪心 -> False solve -> True s1='ab', s2='ab', s3='abab': 贪心 -> True solve -> True s1='a', s2='a', s3='aa': 贪心 -> True solve -> True s1='aab', s2='aac', s3='aacaab': 贪心 -> False solve -> True 随机 20000 组：贪心与正确答案不同的有 1748 组（8.7%）
官方示例（aabcc、dbbca、aadbbcbcac）贪心得到 False，正确答案是 True；aa、ab、abaa 也是：s3 的第一个字符 a 两边都能匹配，贪心固定选了 s1，而正确的交错方式要先用 s2 的 a。ab、ab、abab 和 a、a、aa 里贪心碰巧是对的。在随机的 20000 组数据里（字母只有 a、b，冲突很多），贪心出错的有 1748 组，占 8.7%。
朴素递归在每个"两边都匹配"的位置都要分成两支，同一个（i, j）状态会被重复走很多次。最坏的情形是：s1 和 s2 全是 a，s3 是很多个 a 加一个 b（永远无法成功），必须把所有交错的走法都试遍才能断定不行。下面是真实统计的调用次数：
朴素递归的调用次数（s1、s2 全是 a，s3 = a*(2n-1) + b：无法交错成功，必须试遍所有交错方式）： n= 4: 结果 False，递归调用 181 次， 0.03 ms；动态规划只有 25 个格子 n= 8: 结果 False，递归调用 35749 次， 4.35 ms；动态规划只有 81 个格子 n=10: 结果 False，递归调用 520675 次， 60.44 ms；动态规划只有 121 个格子 n=12: 结果 False，递归调用 7696443 次， 899.17 ms；动态规划只有 169 个格子
n 从 4 到 12，调用次数从 181 增长到 7696443，n = 12 时耗时 899.2ms；每增加 2，大约乘 14 到 15 倍，是指数增长。动态规划只有 (n + 1)² 个格子（n = 12 时 169 个）。
先检查长度：s1 和 s2 的长度之和必须等于 s3 的长度。用一维数组滚动：dp[j] 表示当前行（s1 用了 i 个）、s2 用了 j 个时能否成功，dp[0] 初始为真。对每个 (i, j)（跳过 (0, 0)）：如果 i > 0，并且 dp[j]（上一行的值，即 dp[i-1][j]）为真，并且 s1[i-1] == s3[i+j-1]，成立；如果 j > 0，并且 dp[j-1]（当前行左边，即 dp[i][j-1]）为真，并且 s2[j-1] == s3[i+j-1]，成立；两者任一成立，dp[j] 为真。最后返回 dp[n]。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [False] * (n + 1) # dp[j]：s1 的前 i 个字符和 s2 的前 j 个字符，能否交错组成 s3 的前 i+j 个字符 dp[0] = True for i in range(m + 1): for j in range(n + 1): if i == 0 and j == 0: continue ok = False if i > 0 and dp[j] and s1[i - 1] == s3[i + j - 1]: # 最后一个字符来自 s1（dp[j] 还是上一行的值） ok = True if j > 0 and dp[j - 1] and s2[j - 1] == s3[i + j - 1]: # 最后一个字符来自 s2 ok = True dp[j] = ok return dp[n]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["aabcc","dbbca","aadbbcbcac"] → true ["aabcc","dbbca","aadbbbaccc"] → false ["","",""] → true ["a","","a"] → true ["","b","b"] → true ["a","b","ab"] → true
Java · 解法代码class Solution { public boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(), n = s2.length(); if (m + n != s3.length()) return false; boolean[] dp = new boolean[n + 1]; // dp[j]：s1 的前 i 个和 s2 的前 j 个字符，能否交错组成 s3 的前 i+j 个 dp[0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 && j == 0) continue; boolean ok = false; if (i > 0 && dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ok = true; // 最后一个字符来自 s1 if (j > 0 && dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) ok = true; // 最后一个字符来自 s2 dp[j] = ok; } } return dp[n]; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["aabcc","dbbca","aadbbcbcac"] → true ["aabcc","dbbca","aadbbbaccc"] → false ["","",""] → true ["a","","a"] → true ["","b","b"] → true ["a","b","ab"] → true
Go · 解法代码func isInterleave(s1 string, s2 string, s3 string) bool { m, n := len(s1), len(s2) if m+n != len(s3) { return false } dp := make([]bool, n+1) // dp[j]：s1 的前 i 个和 s2 的前 j 个字符，能否交错组成 s3 的前 i+j 个 dp[0] = true for i := 0; i <= m; i++ { for j := 0; j <= n; j++ { if i == 0 && j == 0 { continue } ok := false if i > 0 && dp[j] && s1[i-1] == s3[i+j-1] { // 最后一个字符来自 s1 ok = true } if j > 0 && dp[j-1] && s2[j-1] == s3[i+j-1] { // 最后一个字符来自 s2 ok = true } dp[j] = ok } } return dp[n] }
$ go build -o bin . && ./bin < cases.jsonl ["aabcc","dbbca","aadbbcbcac"] → true ["aabcc","dbbca","aadbbbaccc"] → false ["","",""] → true ["a","","a"] → true ["","b","b"] → true ["a","b","ab"] → true
JavaScript · 解法代码function isInterleave(s1, s2, s3) { const m = s1.length, n = s2.length; if (m + n !== s3.length) return false; const dp = new Array(n + 1).fill(false); // dp[j]：s1 的前 i 个和 s2 的前 j 个字符，能否交错组成 s3 的前 i+j 个 dp[0] = true; for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i === 0 && j === 0) continue; let ok = false; if (i > 0 && dp[j] && s1[i - 1] === s3[i + j - 1]) ok = true; // 最后一个字符来自 s1 if (j > 0 && dp[j - 1] && s2[j - 1] === s3[i + j - 1]) ok = true; // 最后一个字符来自 s2 dp[j] = ok; } } return dp[n]; }
$ node run.js < cases.jsonl ["aabcc","dbbca","aadbbcbcac"] → true ["aabcc","dbbca","aadbbbaccc"] → false ["","",""] → true ["a","","a"] → true ["","b","b"] → true ["a","b","ab"] → true
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: bool isInterleave(string s1, string s2, string s3) { int m = s1.size(), n = s2.size(); if (m + n != (int)s3.size()) return false; vector<char> dp(n + 1, 0); // dp[j]：s1 的前 i 个和 s2 的前 j 个字符，能否交错组成 s3 的前 i+j 个 dp[0] = 1; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 && j == 0) continue; bool ok = false; if (i > 0 && dp[j] && s1[i - 1] == s3[i + j - 1]) ok = true; // 最后一个字符来自 s1 if (j > 0 && dp[j - 1] && s2[j - 1] == s3[i + j - 1]) ok = true; // 最后一个字符来自 s2 dp[j] = ok; } } return dp[n]; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["aabcc","dbbca","aadbbcbcac"] → true ["aabcc","dbbca","aadbbbaccc"] → false ["","",""] → true ["a","","a"] → true ["","b","b"] → true ["a","b","ab"] → true
共 15 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 15/15 Java 通过 15/15 Go 通过 15/15 JavaScript 通过 15/15 C++ 通过 15/15
s1、s2 长度 n 分别为 10、100、300、1000（全是 a），s3 是 2n - 1 个 a 加一个 b（必然失败，这是朴素递归最慢的情形），每个规模取三次中最快的一次：
s1、s2 的长度 n（全是 a，s3 = a*(2n-1) + b，判定为假） | 暴力解 | 本文解法
10 | 57.594 ms | 0.010 ms
100 | （未测，太慢） | 0.836 ms
300 | （未测，太慢） | 8.308 ms
1000 | （未测，太慢） | 101.437 ms基准（朴素递归）n = 10 时就需要 57.6ms，更大规模没有再测；动态规划从 100 到 300（3 倍）耗时增长约 9.9 倍，从 300 到 1000（3.3 倍）增长约 12.2 倍，符合 O(mn) 的平方增长，n = 1000（100 万个格子）时 101.4ms。
Python 版本另外和朴素递归做了随机对拍：s1、s2 各长 0 到 5、字母取自 a、b；s3 一半是把两个串真正交错得到的（答案一定为真），一半是把两个串的字母随机打乱（长度正确、多数为假）：
随机对拍 30000 组（s1、s2 各长 0 到 5、字母取自 a、b；s3 一半是把两个串真正交错得到的，一半是把两个串的字母随机打乱（长度总是正确）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 15 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 s1 = "aabcc"、s2 = "dbbca"、s3 = "aadbbcbcac"，表格是 6 × 6 的 dp（行是 s1 的前缀长度 0 到 5，列是 s2 的前缀长度 0 到 5），T / F 表示能否交错。每一步说明这个格子的最后一个字符能不能来自 s1 或 s2。右下角是 T，答案为真。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。