LeetCode | Scramble String

 1 class Solution {
 2 public:
 3     bool anagram(string s1, string s2){
 4         if(s1.size() != s2.size()) return false;
 5         sort(s1.begin(), s1.end());
 6         sort(s2.begin(), s2.end());
 7         return s1 == s2;
 8     }
 9     bool isScramble(string s1, string s2) {
10         if (s1.empty() && s2.empty()) return true;
11         if (s1.length() != s2.length()) return false;
12         if (s1 == s2) return true;
13         if (!anagram(s1, s2)) return false;
14         bool ret = false;
15         int n = s1.length();
16         
17         for (int i = 1; i < n; i++) {
18             ret = isScramble(s1.substr(0, i), s2.substr(n - i, i)) && isScramble(s1.substr(i, n - i), s2.substr(0, n - i));
19             if (ret) return true;
20             ret = isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, n - i), s2.substr(i, n - i));
21             if (ret) return true;
22         }
23         return ret;
24     }
25 };