[LeetCode] Scramble String

 1 class Solution {
 2 public:
 3     struct state{
 4         int x1, y1, x2, y2;
 5         state(int x1, int y1,int x2,int y2):x1(x1),y1(y1),x2(x2),y2(y2){}
 6         state():x1(0),x2(0),y1(0),y2(0){}
 7         
 8         bool operator==(const state& rhs) const {
 9             return x1 == rhs.x1 &&
10             x2 == rhs.x2 &&
11             y1 == rhs.y1 &&
12             y2 == rhs.y2;
13         }
14     };
15     
16     struct StateHash {
17         size_t operator()(const state& s) const {
18             return std::hash<int>()(s.x1 + s.x2 * s.x2 + s.y1 * s.y1 * s.y1 + s.y2 * s.y2 * s.y2 * s.y2);
19         }
20     };
21     
22     bool isScramble(string s1, string s2) {
23         unordered_map<state, int, StateHash> states;
24         int n = s1.size();
25         if (s2.size() != n) return false;
26         state final_state(0,n-1,0,n-1);
27         return dfs(s1, s2, final_state, states);
28     }
29     
30     bool dfs(const string& s1, const string& s2, state s, unordered_map<state, int, StateHash>& states) {
31         auto it = states.find(s);
32         if (it != states.end()) return it->second;
33         bool ans = false;
34         if (s.x1 == s.y1) {
35             if (s1[s.x1] == s2[s.x2]) ans = true;
36         } else {
37             for (int i = s.x1; i < s.y1; i++) {
38                 int len = i - s.x1;
39                 if (dfs(s1, s2, state(s.x1, i, s.x2, s.x2 + len), states) && dfs(s1, s2, state(i+1, s.y1, s.x2+len+1, s.y2), states)) {
40                     ans = true;
41                     break;
42                 }
43                 
44                 if (dfs(s1, s2, state(s.x1, i, s.y2-len, s.y2), states) && dfs(s1, s2, state(i+1,s.y1, s.x2, s.y2-len-1), states)) {
45                     ans = true;
46                     break;
47                 }
48             }
49         }
50         
51         return states[s] = ans;
52     }
53 };