1
class Solution {
2
 public:
3
  // checks if s2 is scrambled form of s1
4
  /*
5
      The idea is to find a position in string s1, from where scrambling must
6
     have started to create s2. So if k is the position, then s1[0-k] and
7
     s1[k+1, N-1] were the last scramble op. We do this recursively for the
8
     smaller substrings.
9

10
  */
11
  bool isScrambled(int s1_start, int s1_end, int s2_start, int s2_end, string &s1, string &s2,
12
                   unordered_map<string, bool> &dp) {
13
    // create the current position combination
14
    string curr_cmb = to_string(s1_start) + ',' + to_string(s1_end) + ',' + to_string(s2_start) +
15
                      ',' + to_string(s2_end);
16
    // check if the values is in cache
17
    auto it = dp.find(curr_cmb);
18
    if (it != dp.end()) return dp[curr_cmb];
19

20
    // base cases
21
    if (s1_end < s1_start || s2_end < s2_start) return false;
22
    // if the size of two strings is diff, then scrambling not poss
23
    if (s1_end - s1_start != s2_end - s2_start) return false;
24
    // if the two substrings match, then they are scrambled
25
    if (s1.substr(s1_start, s1_end - s1_start + 1) == s2.substr(s2_start, s2_end - s2_start + 1))
26
      return true;
27

28
    // check if the two substrings contains the same set of chars
29
    vector<int> char_freq(256, 0);
30
    for (int i = 0; i <= s1_end - s1_start; i++)
31
      char_freq[s1[s1_start + i] - 'a']++, char_freq[s2[s2_start + i] - 'a']--;
32
    for (int i = 0; i < 256; i++)
33
      if (char_freq[i]) return false;
34

35
    // find a position which is the potential scramble point
36
    for (int k = 0; k < (s1_end - s1_start); k++) {
37
      // check for s1[start: k], s2[start:k] and s1[k+1 : end], s2[k+1 : end]
38
      if (isScrambled(s1_start, s1_start + k, s2_start, s2_start + k, s1, s2, dp) &&
39
          isScrambled(s1_start + k + 1, s1_end, s2_start + k + 1, s2_end, s1, s2, dp))
40
        return dp[curr_cmb] = true;
41
      // Now incase of s2, maybe scramble opertation was performed at k, so
42
      // now check if the other half of s2
43
      // check for s1[start: k], s2[end - k : end] and s1[k+1 : end], s2[s : end
44
      // - k - 1]
45
      if (isScrambled(s1_start, s1_start + k, s2_end - k, s2_end, s1, s2, dp) &&
46
          isScrambled(s1_start + k + 1, s1_end, s2_start, s2_end - k - 1, s1, s2, dp))
47
        return dp[curr_cmb] = true;
48
    }
49
    return dp[curr_cmb] = false;
50
  }
51

52
  bool isScramble(string s1, string s2) {
53
    // DP cache: saves the result of (s1_start, s1_end, s2_start, s2_end) cmb
54
    unordered_map<string, bool> dp;
55
    return isScrambled(0, s1.size() - 1, 0, s2.size() - 1, s1, s2, dp);
56
  }
57
};