给你两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
解析
记忆化递归：枚举分割点，检查两种交换方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var isScramble = function (s1, s2) {
const memo = new Map();
function dfs(a, b) {
if (a === b) return true;
const key = a + '#' + b;
if (memo.has(key)) return memo.get(key);
if (a.length !== b.length || [...a].sort().join('') !== [...b].sort().join('')) {
memo.set(key, false); return false;
}
const n = a.length;
for (let i = 1; i < n; i++) {
if ((dfs(a.slice(0, i), b.slice(0, i)) && dfs(a.slice(i), b.slice(i))) ||
(dfs(a.slice(0, i), b.slice(n - i)) && dfs(a.slice(i), b.slice(0, n - i)))) {
memo.set(key, true); return true;
}
}
memo.set(key, false); return false;
}
return dfs(s1, s2);
};
|