To solve this problem, you first need to understand it well. The key problem is tell the difference of scramble from permutations. You may refer to this link for some nice discussions. Then you can proceed to solve it. This link posts a very easy and also very fast code, which is very readable. I almost copy it below.
1 class Solution { 2 public: 3 bool isScramble(string s1, string s2) { 4 if (s1 == s2) return true; 5 int n = s1.length(); 6 int counts[26] = {0}; 7 for (int i = 0; i < n; i++) { 8 counts[s1[i] - 'a']++; 9 counts[s2[i] - 'a']--; 10 } 11 for (int i = 0; i < 26; i++) 12 if (counts[i]) return false; 13 for (int i = 1; i < n; i++) { 14 if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) 15 return true; 16 if (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i))) 17 return true; 18 } 19 return false; 20 } 21 };
