87. Scramble String

Recursively partition two strings into four parts and compare those four parts. For each comparison, if two strings are only scrambled, they must have all the same letters. So we can use hash map to do the check.

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