京公网安备11010502063487号把一个字符串按下面的规则"扰乱"：如果长度是 1，停止；否则在某个位置把它切成两个非空子串 x 和 y，可以选择交换它们（得到 y + x）或者不交换（x + y），然后对 x 和 y 递归地做同样的操作。给定两个长度相同的字符串 s1 和 s2，判断 s2 是否可以由 s1 扰乱得到。直接按定义递归，每个位置有"交换"和"不交换"两种选择，规模会随长度指数增长。有两个关键的优化：记忆化（同一对子串只判断一次）和剪枝（两个子串的字母组成不同，一定不可能）。本文用真实统计的调用次数展示这两个优化的效果，给出五种语言的实现，并把递归的判断过程做成分步演示。
完整题目见官方页面（链接在文末）。两个字符串长度相同，只含小写字母。基准解是完全按定义写的朴素递归，没有任何记忆化和剪枝：判断两个子串相等就返回真，否则枚举切分位置，对"不交换"和"交换"两种情形都递归，与带优化的解法是同一个定义的两种实现方式。一共 14 组用例，覆盖：官方两个示例、单个字符、长度 2、逆序、有重复字母的字符串：
输入 ["great","rgeat"] 输出 true 输入 ["abcde","caebd"] 输出 false 输入 ["a","a"] 输出 true 输入 ["ab","ba"] 输出 true 输入 ["ab","ab"] 输出 true 输入 ["abc","bca"] 输出 true
我构造了最坏的情形：s1 是 abcdefg...，s2 是它的一个字母相同但不是扰乱关系的排列（在固定随机种子下找到的第一个非扰乱排列）。这时朴素递归必须试遍所有切法才能断定"不行"。下面是朴素递归的真实调用次数，与带记忆化和剪枝时真正需要计算的状态数：
朴素递归（无记忆化、无剪枝）的调用次数 vs 带记忆化和剪枝时真正需要计算的状态数；s2 是 s1 的一个非扰乱排列（最坏情形）： n=5: s2='becad': 结果 False，朴素递归调用 110 次；记忆化 + 剪枝的状态数 9；solve -> False n=6: s2='bfaecd': 结果 False，朴素递归调用 318 次；记忆化 + 剪枝的状态数 11；solve -> False n=7: s2='bfgaecd': 结果 False，朴素递归调用 963 次；记忆化 + 剪枝的状态数 13；solve -> False n=8: s2='cfbeaghd': 结果 False，朴素递归调用 2963 次；记忆化 + 剪枝的状态数 15；solve -> False
朴素递归的调用次数 n = 5 时是 110 次，n = 6、7、8 分别是 318、963、2963 次，每增加一个字符大约乘 3，是指数增长。带记忆化和剪枝时，需要计算的（不同的）状态只有 9 到 15 个（n = 5 到 8）。原因是剪枝很有力：大部分切分出来的子串对字母组成就不同，直接判否，不再继续递归。这个对比只用了这四组固定种子的数据，最坏的输入可能不同，但趋势是明确的。
dfs(i, j, L) 表示 s1 从下标 i 起长 L 的子串，能否扰乱成 s2 从下标 j 起长 L 的子串。先查缓存；两个子串相等返回真；字母的多重集合不同返回假；否则枚举切分位置 k（1 到 L-1），尝试两种情形：不交换（dfs(i, j, k) 且 dfs(i+k, j+k, L-k)）和交换（dfs(i, j+L-k, k) 且 dfs(i+k, j, L-k)），任一成立就返回真。状态一共有 O(n³) 个（i、j、L），每个状态枚举 O(n) 个切分位置，所以是 O(n⁴)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java、Go、C++ 用三维数组做缓存，JavaScript 用 Map。
Python · 解法代码def solve(s1, s2): n = len(s1) if n != len(s2): return False memo = {} def dfs(i, j, L): # s1[i:i+L] 能否扰乱成 s2[j:j+L] key = (i, j, L) if key in memo: return memo[key] a, b = s1[i:i + L], s2[j:j + L] if a == b: res = True elif sorted(a) != sorted(b): # 字母的多重集合不同，一定不行：提前剪枝 res = False else: res = False for k in range(1, L): # 在第 k 个字符处切开 if (dfs(i, j, k) and dfs(i + k, j + k, L - k)) or \ (dfs(i, j + L - k, k) and dfs(i + k, j, L - k)): # 不交换 / 交换两段 res = True break memo[key] = res return res return dfs(0, 0, n)
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["great","rgeat"] → true ["abcde","caebd"] → false ["a","a"] → true ["ab","ba"] → true ["ab","ab"] → true ["abc","bca"] → true
Java · 解法代码class Solution { private String s1, s2; private byte[][][] memo; // memo[i][j][L]：0 还没算，1 是 True，2 是 False public boolean isScramble(String s1, String s2) { int n = s1.length(); if (n != s2.length()) return false; this.s1 = s1; this.s2 = s2; memo = new byte[n][n][n + 1]; return dfs(0, 0, n); } private boolean dfs(int i, int j, int len) { // s1[i, i+len) 能否扰乱成 s2[j, j+len) if (memo[i][j][len] != 0) return memo[i][j][len] == 1; boolean res = false; if (s1.regionMatches(i, s2, j, len)) { res = true; } else if (sameLetters(i, j, len)) { // 字母的多重集合不同，一定不行：提前剪枝 for (int k = 1; k < len && !res; k++) { // 在第 k 个字符处切开 if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) || (dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) res = true; // 不交换 / 交换两段 } } memo[i][j][len] = (byte) (res ? 1 : 2); return res; } private boolean sameLetters(int i, int j, int len) { int[] cnt = new int[128]; for (int k = 0; k < len; k++) { cnt[s1.charAt(i + k)]++; cnt[s2.charAt(j + k)]--; } for (int c : cnt) if (c != 0) return false; return true; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["great","rgeat"] → true ["abcde","caebd"] → false ["a","a"] → true ["ab","ba"] → true ["ab","ab"] → true ["abc","bca"] → true
Go · 解法代码func isScramble(s1 string, s2 string) bool { n := len(s1) if n != len(s2) { return false } memo := make([][][]int8, n) // memo[i][j][L]：0 还没算，1 是 True，2 是 False for i := range memo { memo[i] = make([][]int8, n) for j := range memo[i] { memo[i][j] = make([]int8, n+1) } } sameLetters := func(i, j, l int) bool { var cnt [128]int for k := 0; k < l; k++ { cnt[s1[i+k]]++ cnt[s2[j+k]]-- } for _, c := range cnt { if c != 0 { return false } } return true } var dfs func(i, j, l int) bool // s1[i:i+l] 能否扰乱成 s2[j:j+l] dfs = func(i, j, l int) bool { if memo[i][j][l] != 0 { return memo[i][j][l] == 1 } res := false if s1[i:i+l] == s2[j:j+l] { res = true } else if sameLetters(i, j, l) { // 字母的多重集合不同，一定不行：提前剪枝 for k := 1; k < l && !res; k++ { // 在第 k 个字符处切开 if (dfs(i, j, k) && dfs(i+k, j+k, l-k)) || (dfs(i, j+l-k, k) && dfs(i+k, j, l-k)) { // 不交换 / 交换两段 res = true } } } if res { memo[i][j][l] = 1 } else { memo[i][j][l] = 2 } return res } return dfs(0, 0, n) }
$ go build -o bin . && ./bin < cases.jsonl ["great","rgeat"] → true ["abcde","caebd"] → false ["a","a"] → true ["ab","ba"] → true ["ab","ab"] → true ["abc","bca"] → true
JavaScript · 解法代码function isScramble(s1, s2) { const n = s1.length; if (n !== s2.length) return false; const memo = new Map(); // 键 "i,j,L" → 结果 const sameLetters = (i, j, len) => { const cnt = new Array(128).fill(0); for (let k = 0; k < len; k++) { cnt[s1.charCodeAt(i + k)]++; cnt[s2.charCodeAt(j + k)]--; } return cnt.every((c) => c === 0); }; const dfs = (i, j, len) => { // s1[i, i+len) 能否扰乱成 s2[j, j+len) const key = i + "," + j + "," + len; if (memo.has(key)) return memo.get(key); let res = false; if (s1.substr(i, len) === s2.substr(j, len)) { res = true; } else if (sameLetters(i, j, len)) { // 字母的多重集合不同，一定不行：提前剪枝 for (let k = 1; k < len && !res; k++) { // 在第 k 个字符处切开 if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) || (dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) res = true; // 不交换 / 交换两段 } } memo.set(key, res); return res; }; return dfs(0, 0, n); }
$ node run.js < cases.jsonl ["great","rgeat"] → true ["abcde","caebd"] → false ["a","a"] → true ["ab","ba"] → true ["ab","ab"] → true ["abc","bca"] → true
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { string s1, s2; vector<vector<vector<signed char>>> memo; // memo[i][j][L]：0 还没算，1 是 True，2 是 False bool sameLetters(int i, int j, int len) { int cnt[128] = {0}; for (int k = 0; k < len; k++) { cnt[(int)s1[i + k]]++; cnt[(int)s2[j + k]]--; } for (int c : cnt) if (c != 0) return false; return true; } bool dfs(int i, int j, int len) { // s1[i, i+len) 能否扰乱成 s2[j, j+len) if (memo[i][j][len] != 0) return memo[i][j][len] == 1; bool res = false; if (s1.compare(i, len, s2, j, len) == 0) { res = true; } else if (sameLetters(i, j, len)) { // 字母的多重集合不同，一定不行：提前剪枝 for (int k = 1; k < len && !res; k++) { // 在第 k 个字符处切开 if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) || (dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) res = true; // 不交换 / 交换两段 } } memo[i][j][len] = res ? 1 : 2; return res; } public: bool isScramble(string a, string b) { int n = a.size(); if (n != (int)b.size()) return false; s1 = a; s2 = b; memo.assign(n, vector<vector<signed char>>(n, vector<signed char>(n + 1, 0))); return dfs(0, 0, n); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["great","rgeat"] → true ["abcde","caebd"] → false ["a","a"] → true ["ab","ba"] → true ["ab","ab"] → true ["abc","bca"] → true
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
s1 是 abcd...，s2 是它的非扰乱排列（同上），n 从 5 到 16，每个规模取三次中最快的一次：
字符串长度 n（s1 = abc…，s2 是它的一个非扰乱排列：必须试遍所有切法才能断定不行） | 暴力解 | 本文解法
5 | 0.019 ms | 0.005 ms
6 | 0.048 ms | 0.006 ms
7 | 0.141 ms | 0.007 ms
8 | （未测，太慢） | 0.008 ms
12 | （未测，太慢） | 0.014 ms
16 | （未测，太慢） | 0.025 ms基准（朴素递归）从 n = 5 到 n = 7 耗时增长约 8 倍（0.016ms、0.044ms、0.130ms），n = 8 及以上没有再测；本文解法在 n = 16 时也只要 0.020ms。因为这组数据里剪枝让大部分状态立刻被判否，所以耗时几乎不随 n 增长；理论上最坏的情形（字母大量重复、剪枝失效）会更慢，这里没有测。
Python 版本另外和朴素递归做了随机对拍：长 1 到 7、字母取自 a、b、c，一半是同一组字母的随机排列，一半完全随机：
随机对拍 5000 组（长 1 到 7、字母取自 a、b、c 的字符串对（一半是同一组字母的随机排列，一半完全随机）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例。缩进表示递归的深度。第一次在第 1 个字符处切开：g | reat，不交换（g↔r）和交换（g↔t）都因为字母不同被剪枝；再在第 2 个字符处切开：gr | eat，不交换要判断 gr↔rg 和 eat↔eat——gr 和 rg 字母相同，再切开，交换后 g↔g、r↔r 都相同，成立；eat 与 eat 相同，成立。所以 great 可以扰乱成 rgeat。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。