leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0087.cpp (877B)

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 };