leetcode

commit 9a0d9277f267db3bc5581c3a328ff5712a3d5424
parent e858793a144cf47b2530fc4148ddebab400d1af8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 15 Mar 2024 11:57:46 +0000

1 Random Problem

Diffstat:
A
Problems/0756.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/0756.cpp b/Problems/0756.cpp
@@ -0,0 +1,43 @@
+class Solution {
+    vector<char> next[6][6];
+    unordered_map<string, bool> seen;
+
+    bool rec(const string &bottom) {
+        if (bottom.size() == 1) return true;
+        if (seen.count(bottom)) return seen[bottom];
+
+        vector<string> prev, crnt;
+        for (int i = 1; i < size(bottom); i++) {
+            const int c = bottom[i - 1] - 'A', n = bottom[i] - 'A';
+            for (const char c : next[c][n]) {
+                if (prev.empty()) {
+                    crnt.push_back(string(1, c));
+                    continue;
+                }
+                for (const auto &s : prev) {
+                    if (next[s.back() - 'A'][c - 'A'].empty()) continue;
+                    crnt.push_back(s + c);
+                }
+            }
+            if (crnt.empty()) return false;
+
+            prev = crnt;
+            crnt.clear();
+        }
+
+        bool res = false;
+        for (const auto &s : prev) {
+            if (!rec(s)) continue;
+            res = true;
+            break;
+        }
+        return seen[bottom] = res;
+    }
+
+  public:
+    bool pyramidTransition(const string &bottom, const vector<string> &allowed) {
+        for (const auto &s : allowed)
+            next[s[0] - 'A'][s[1] - 'A'].push_back(s[2]);
+        return rec(bottom);
+    }
+};
diff --git a/README.md b/README.md
@@ -464,6 +464,7 @@ for solving problems.
 |  0746  |    Easy    | [Min Cost Climbing Stairs](Problems/0746.cpp)                                                      |
 |  0747  |    Easy    | [Largest Number At Least Twice of Others](Problems/0747.cpp)                                       |
 |  0752  |   Medium   | [Open the Lock](Problems/0752.cpp)                                                                 |
+|  0756  |   Medium   | [Pyramid Transition Matrix](Problems/0756.cpp)                                                     |
 |  0763  |   Medium   | [Partition Labels](Problems/0763.cpp)                                                              |
 |  0767  |   Medium   | [Reorganize String](Problems/0767.cpp)                                                             |
 |  0769  |   Medium   | [Max Chunks To Make Sorted](Problems/0769.cpp)                                                     |