Notes:

1. Make a array to check whether they have same number of chars (s1[i] - 'a') and (s2[i] - 'a')

2. When finally check, the i start from 1.

3. It is scramble as comparing s1(0, i) with s2(size - i, i) and s1(i) with s2(0, size-i). Kind of symmetry.

 

1 class Solution { 2 public: 3     bool isScramble(string s1, string s2) { 4         if (s1.size() != s2.size()) return false; 5         vector
     
       rec(26, 0); 6         for (int i = 0; i < s1.size(); i++) { 7             rec[s1[i] - 'a']++; 8             rec[s2[i] - 'a']--; 9         }10         for (int i = 0; i < 26; i++) {11             if (rec[i] != 0) return false;12         }13         if (s1.size() == 1 && s2.size() == 1) return true;14         for (int i = 1; i < s1.size(); i++) {15             bool result = isScramble(s1.substr(0, i), s2.substr(0, i)) &&16                           isScramble(s1.substr(i), s2.substr(i));17             result |= isScramble(s1.substr(0, i), s2.substr(s2.size()-i, i)) &&18                       isScramble(s1.substr(i), s2.substr(0, s2.size()-i));19             if (result) return true;20         }21         return false;22     }23 };