1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 * Determine if s2 is a scrambled string of s1.
 * @param {string} s1 - The first string
 * @param {string} s2 - The second string
 * @return {boolean} - True if s2 is a scrambled string of s1, otherwise false
 */
function isScramble(s1, s2) {
  // Base cases
  if (s1 === s2) return true;
  if (s1.length !== s2.length) return false;
  
  // Check if the strings have the same character frequencies
  if ([...s1].sort().join('') !== [...s2].sort().join('')) return false;
  
  // Create a memoization map
  const memo = new Map();
  
  function isScrambleHelper(s1, s2) {
    // Create a key for the memoization map
    const key = s1 + '|' + s2;
    
    // Check if we've already computed this result
    if (memo.has(key)) return memo.get(key);
    
    // Base case
    if (s1 === s2) {
      memo.set(key, true);
      return true;
    }
    
    // Check character frequencies
    if ([...s1].sort().join('') !== [...s2].sort().join('')) {
      memo.set(key, false);
      return false;
    }
    
    const n = s1.length;
    
    // Try all possible split positions
    for (let i = 1; i < n; i++) {
      // Check if we can get s2 by keeping the order of substrings
      if (isScrambleHelper(s1.substring(0, i), s2.substring(0, i)) && 
          isScrambleHelper(s1.substring(i), s2.substring(i))) {
        memo.set(key, true);
        return true;
      }
      
      // Check if we can get s2 by swapping the substrings
      if (isScrambleHelper(s1.substring(0, i), s2.substring(n - i)) && 
          isScrambleHelper(s1.substring(i), s2.substring(0, n - i))) {
        memo.set(key, true);
        return true;
      }
    }
    
    memo.set(key, false);
    return false;
  }
  
  return isScrambleHelper(s1, s2);
}
 
// Dynamic Programming Approach
function isScrambleDP(s1, s2) {
  // Base cases
  if (s1 === s2) return true;
  if (s1.length !== s2.length) return false;
  
  // Check if the strings have the same character frequencies
  if ([...s1].sort().join('') !== [...s2].sort().join('')) return false;
  
  const n = s1.length;
  
  // Create a 3D DP array
  const dp = Array(n).fill().map(() => 
    Array(n).fill().map(() => 
      Array(n + 1).fill(false)
    )
  );
  
  // Base case: substrings of length 1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      dp[i][j][1] = s1[i] === s2[j];
    }
  }
  
  // Fill the DP array for substrings of length 2 to n
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      for (let j = 0; j <= n - length; j++) {
        for (let k = 1; k < length; k++) {
          // Check if we can get s2 by keeping the order of substrings
          if (dp[i][j][k] && dp[i + k][j + k][length - k]) {
            dp[i][j][length] = true;
            break;
          }
          
          // Check if we can get s2 by swapping the substrings
          if (dp[i][j + length - k][k] && dp[i + k][j][length - k]) {
            dp[i][j][length] = true;
            break;
          }
        }
      }
    }
  }
  
  return dp[0][0][n];
}
 
// Test cases
console.log(isScramble("great", "rgeat")); // Output: true
console.log(isScramble("abcde", "caebd")); // Output: false
console.log(isScramble("a", "a")); // Output: true
 
console.log(isScrambleDP("great", "rgeat")); // Output: true
console.log(isScrambleDP("abcde", "caebd")); // Output: false
console.log(isScrambleDP("a", "a")); // Output: true