前言LeetCode 87 的定义是把一个字符串递归地切成两个非空部分可以选择交换这两部分的位置也可以不交换然后对两部分继续同样的操作。能通过这种方式得到的字符串称为原串的一个「搅乱字符串」scramble。给定两个等长字符串判断后者是否是前者的搅乱。常见误解有三个。第一以为只能在中间切一刀。实际上切点可以是任意位置只要两段都非空。第二以为只需考虑「交换」或「不交换」中的一种。递归定义里两种情况都可能发生而且不同层可以做出不同选择。第三以为字符集相同就一定是搅乱实际上字符集相同只是必要条件远不是充分条件。本文给出带记忆化的递归实现并解释两个关键剪枝长度与字符计数。代码以 C17 为准。一、递归定义设原串为a、目标串为b长度都为 n。n 1 时a b即为真。n 1 时枚举切点 k1 ≤ k n把a切成a1 a[0, k)与a2 a[k, n)。有两种对应方式不交换a1对应b[0, k)a2对应b[k, n)交换a1对应b[n-k, n)a2对应b[0, n-k)。任一种方式下两对子串都满足「前者是后者的搅乱」则整体为真。这里的「对应」必须是同长度的子串否则字符数不可能匹配。切点枚举覆盖了所有可能的切法因为递归定义允许在任意位置切分并交换。当 n 1 时切分循环不会执行结果完全由a b决定这也是递归的终止条件。二、两个剪枝第一长度不同直接返回假。第二字符计数不同直接返回假。后者是递归里最重要的剪枝如果两个子串的字符多重集不同无论怎么切都不可能匹配没必要继续枚举切点。字符计数用长度 26 的数组即可题目限定小写字母。计数相同只是必要条件仍然需要递归验证顺序但它能砍掉大量明显不可能的分支。第三个隐式剪枝是「完全相同直接返回真」。如果a b不切分也能得到直接成功省掉一整棵子树。以a great、b rgeat为例取 k 2不交换a1 gr对应b的前两个字符rga2 eat对应b的后三个字符eat。递归gr与rg时取 k 1 并交换得到真eat与eat完全相等直接为真。两部分都真整体为真。反过来a abc、b bca的字符计数完全相同但枚举所有切点都找不到对应k 1 时单字符不匹配k 2 时两段的字符集也不匹配最终为假。这说明计数剪枝只能排除一部分情况不能替代结构验证。三、记忆化实现同一个子串对可能在不同的切分路径下反复出现记忆化把结果存起来避免重复计算。键可以用「两个子串 分隔符」拼成字符串。// 适用于 C17#include array#include string#include string_view#include unordered_mapclass Solution {public:bool isScramble(std::string_view a, std::string_view b) {if (a.size() ! b.size()) return false;memo_.clear();return solve(a, b);}private:bool solve(std::string_view a, std::string_view b) {if (a b) return true;std::arrayint, 26 count{};for (char c : a) count[static_caststd::size_t(c - a)];for (char c : b) --count[static_caststd::size_t(c - a)];for (int v : count)if (v ! 0) return false;const std::string key std::string(a) # std::string(b);const auto it memo_.find(key);if (it ! memo_.end()) return it-second;const std::size_t n a.size();for (std::size_t k 1; k n; k) {// 不交换a 的前 k 个对应 b 的前 k 个if (solve(a.substr(0, k), b.substr(0, k)) solve(a.substr(k), b.substr(k))) {return memo_[key] true;}// 交换a 的前 k 个对应 b 的后 k 个if (solve(a.substr(0, k), b.substr(n - k)) solve(a.substr(k), b.substr(0, n - k))) {return memo_[key] true;}}return memo_[key] false;}std::unordered_mapstd::string, bool memo_;};std::string_view::substr返回视图不复制字符只有构造 memo 键时才复制。分隔符#不在小写字母范围内因此a # b的拼接不会产生歧义给定一个键能唯一还原出a和b。如果字符集可能包含#就要改用长度前缀例如先写入长度再加内容否则不同的子串对可能拼出同一个键。memo_是类的成员每次调用isScramble先清空避免不同测试用例之间串结果。这在 LeetCode 这类「一个对象多次调用」的环境里很重要。四、复杂度与优化设字符串长度为 n。状态由「a 的某个子串 b 的某个子串」确定每个子串由起点和长度刻画因此状态数是 O(n³)每个状态枚举 O(n) 个切点总时间 O(n⁴)。空间上memo 最多存 O(n³) 个键每个键保存一份长度为 O(n) 的字符串最坏 O(n⁴) 字节。题目规模通常很小n ≤ 30这个量级可以接受。如果想进一步优化可以用三维数组代替字符串键把状态编码成(i, j, len)查找从哈希变成 O(1) 下标访问省掉键的构造与复制。预计算两个串的前缀字符计数使每次字符计数检查从 O(n) 降到 O(1)。先做一次全局字符计数不同直接返回假。方案时间空间说明纯递归指数级O(n) 栈大量重复子问题记忆化字符串键O(n⁴)O(n⁴) 字节实现直观记忆化下标键O(n⁴)O(n³)省去键构造区间 DPO(n⁴)O(n³)自底向上无递归栈区间 DP 的思路是dp[i][j][len]表示a从 i 开始、b从 j 开始、长度为 len 的两个子串是否互为搅乱。按长度从小到大填表转移与递归式相同。它的好处是没有递归深度问题坏处是要开三维数组且必须按长度顺序计算。常见坑点❌ 只尝试在中间切分漏掉其他切点。✅ 枚举 1 到 n-1 的所有 k。❌ 只检查「不交换」的情况。✅ 同时检查交换对应两种都要递归。❌ 不做字符计数剪枝大量无效分支导致超时。✅ 每次递归先比较 26 个字母的计数。❌ memo 键用简单拼接且字符集包含分隔符产生键碰撞。✅ 用不可能出现的分隔符或加长度前缀或直接用下标作键。❌ 认为字符集相同就是搅乱。✅ 计数相同只是必要条件还要递归验证结构。❌memo_在多次调用之间不清空测试用例互相污染。✅ 每次入口清空或把 memo 作为局部变量传递。❌ 让 k 取 0 或 n产生空子串。✅ 切分要求两段非空k 取 1 到 n-1。❌ 递归里反复std::string拷贝子串。✅ 用string_view传递只在需要作键时复制。总结要点结论切分任意位置两段非空对应不交换与交换两种剪枝长度、字符计数、完全相等记忆化子串对作键避免重复复杂度时间 O(n⁴)状态 O(n³)这道题的递归式很短难在「两种对应方式都要枚举」和「剪枝要到位」。把切点范围、交换对应的下标、计数检查这三处写对再加一层记忆化代码就能在题目规模内稳定工作。