leetcode

0 class Solution {

1 unordered_map<string, bool> um;

2

3 public:

4 bool isScramble(string s1, string s2) {

5 if (um.count(s1 + s2)) return um[s1 + s2];

6 if (s1.size() != s2.size()) return false;

7 if (s1 == s2) return true;

8

9 vector<int> count(128, 0);

10 int n = s1.size();

11 um[s1 + s2] = false;

12

13 for (int i = 0; i < n; i++)

14 count[s1[i]]++, count[s2[i]]--;

15 for (int n : count)

16 if (n) return false;

17

18 for (int k = 1; k < n; k++) {

19 if (isScramble(s1.substr(0, k), s2.substr(0, k)) && isScramble(s1.substr(k), s2.substr(k)) ||

20 isScramble(s1.substr(0, k), s2.substr(n - k)) &&

21 isScramble(s1.substr(k), s2.substr(0, n - k))) {

22 um[s1 + s2] = true;

23 return true;

24 }

25 }

26 return false;

27 }

28 };