leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0087.cpp (877B)

      1 class Solution {
      2     unordered_map<string, bool> um;
      3 
      4   public:
      5     bool isScramble(string s1, string s2) {
      6         if (um.count(s1 + s2)) return um[s1 + s2];
      7         if (s1.size() != s2.size()) return false;
      8         if (s1 == s2) return true;
      9 
     10         vector<int> count(128, 0);
     11         int n = s1.size();
     12         um[s1 + s2] = false;
     13 
     14         for (int i = 0; i < n; i++)
     15             count[s1[i]]++, count[s2[i]]--;
     16         for (int n : count)
     17             if (n) return false;
     18 
     19         for (int k = 1; k < n; k++) {
     20             if (isScramble(s1.substr(0, k), s2.substr(0, k)) && isScramble(s1.substr(k), s2.substr(k)) ||
     21                 isScramble(s1.substr(0, k), s2.substr(n - k)) &&
     22                     isScramble(s1.substr(k), s2.substr(0, n - k))) {
     23                 um[s1 + s2] = true;
     24                 return true;
     25             }
     26         }
     27         return false;
     28     }
     29 };