1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

int cmp(char a,char b) {
    return a < b;
}
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.length() != s2.length())return false;
        string s1t = s1;
        string s2t = s2;
        sort(s1.begin(),s1.end(),cmp);
        sort(s2.begin(),s2.end(),cmp);
        if(s1 != s2)return false;
        return checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
    }
private:
    bool checkIs(string s1,string s2) {
        if(s1.length() <= 0)return true;
        if(s1.length() == 1) {
            if(s1[0] == s2[0])return true;
            else return false;
        }
        int i = 0;
        while(i < s1.length()) {
            if(s2[i] != s1[0]) {
                i++;
                continue;
            }
            string s1b(s1,1,i);
            string s2b(s2,0,i);
            sort(s1b.begin(),s1b.end(),cmp);
            sort(s2b.begin(),s2b.end(),cmp);
            if(s1b != s2b) {
                i++;
                continue;
            }
            else
                break;
        }
        if(i == s1.length())return false;
        if(i == s1.length()-1) {
            string s1t = string(s1,1,i);
            string s2t = string(s2,0,i);
            return checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
        }
        string s1e(s1,i+1);
        string s2e(s2,i+1);
        sort(s1e.begin(),s1e.end(),cmp);
        sort(s2e.begin(),s2e.end(),cmp);
        if(s1e != s2e)return false;
        string s1t = string(s1,1,i);
        string s2t = string(s2,0,i);
        bool flag1 = checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend())); 
        s1t = string(s1,i+1);
        s2t = string(s2,i+1);
        bool flag2 = checkIs(s1t,s2t) || checkIs(s2t,s1t) || checkIs(string(s1t.rbegin(),s1t.rend()),s2t) || checkIs(s2t,string(s1t.rbegin(),s1t.rend()));
        return flag1 && flag2;
    }
};