1
/**
2
 * The recursive solution with memoization.
3
 * This solution doesn't use `string.slice()`, but pass substring boundaries directly to function calls.
4
 *
5
 * Time Complexity:  O(n^2)
6
 * Space Complexity: O(n^2)
7
 *
8
 * @param {string} s1
9
 * @param {string} s2
10
 * @return {boolean}
11
 */
12
var isScramble = function (s1, s2) {
13
  return checkScramble(s1, 0, s1.length, s2, 0, s2.length);
14
};
15

16
function checkScramble(string1, i1, j1, string2, i2, j2, memory = {}) {
17
  const n = j1 - i1;
18
  const key = 1e9 * i1 + 1e6 * j1 + 1e3 * i2 + 1 * j2;
19

20
  if (key in memory) {
21
    return memory[key];
22
  }
23

24
  let codesum = 0;
25

26
  for (let i = 0; i < n; i++) {
27
    codesum +=
28
      string1.charCodeAt(i1 + i) ** 2 - string2.charCodeAt(i2 + i) ** 2;
29
  }
30

31
  if (codesum !== 0) {
32
    return (memory[key] = false);
33
  }
34

35
  if (n === 1) {
36
    return (memory[key] = true);
37
  }
38

39
  for (let i = 1; i < n; i++) {
40
    if (
41
      checkScramble(string1, i1, i1 + i, string2, i2, i2 + i, memory) &&
42
      checkScramble(string1, i1 + i, j1, string2, i2 + i, j2, memory)
43
    ) {
44
      return (memory[key] = true);
45
    }
46

47
    if (
48
      checkScramble(string1, i1, i1 + i, string2, j2 - i, j2, memory) &&
49
      checkScramble(string1, i1 + i, j1, string2, i2, j2 - i, memory)
50
    ) {
51
      return (memory[key] = true);
52
    }
53
  }
54

55
  return (memory[key] = false);
56
}