leetcode

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

0756.cpp (1271B)

      1 class Solution {
      2     vector<char> next[6][6];
      3     unordered_map<string, bool> seen;
      4 
      5     bool rec(const string &bottom) {
      6         if (bottom.size() == 1) return true;
      7         if (seen.count(bottom)) return seen[bottom];
      8 
      9         vector<string> prev, crnt;
     10         for (int i = 1; i < size(bottom); i++) {
     11             const int c = bottom[i - 1] - 'A', n = bottom[i] - 'A';
     12             for (const char c : next[c][n]) {
     13                 if (prev.empty()) {
     14                     crnt.push_back(string(1, c));
     15                     continue;
     16                 }
     17                 for (const auto &s : prev) {
     18                     if (next[s.back() - 'A'][c - 'A'].empty()) continue;
     19                     crnt.push_back(s + c);
     20                 }
     21             }
     22             if (crnt.empty()) return false;
     23 
     24             prev = crnt;
     25             crnt.clear();
     26         }
     27 
     28         bool res = false;
     29         for (const auto &s : prev) {
     30             if (!rec(s)) continue;
     31             res = true;
     32             break;
     33         }
     34         return seen[bottom] = res;
     35     }
     36 
     37   public:
     38     bool pyramidTransition(const string &bottom, const vector<string> &allowed) {
     39         for (const auto &s : allowed)
     40             next[s[0] - 'A'][s[1] - 'A'].push_back(s[2]);
     41         return rec(bottom);
     42     }
     43 };