We are stacking blocks to form a pyramid. Each block has a color which is a one letter string.
We are allowed to place any color block C on top of two adjacent blocks of colors A and B, if and only if ABC is an allowed triple.
We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.
Return true if we can build the pyramid all the way to the top, otherwise false.
Example 1:
Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
A
/
G E
/ \ /
B C D
We are allowed to place G on top of B and C because BCG is an allowed triple. Similarly, we can place E on top of C and D, then A on top of G and E.
Example 2:
Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"] Output: false Explanation: We can't stack the pyramid to the top. Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
Note:
bottom will be a string with length in range [2, 8]. allowed will have length in range [0, 200]. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.
// 4ms, 95%
class Solution {
bool check(const string& bottom, int i, string next, const vector<vector<int>>& allowedChars) {
if (bottom.size() == 1)
return true;
if (i >= bottom.size() - 1) {
return check(next, 0, "", allowedChars);
}
int mask = allowedChars[bottom[i]-'A'][bottom[i+1] - 'A'];
if (mask != 0) {
for (int j = 0; j < 7; j++) {
if ((mask & (1 << j)) > 0) {
if (check(bottom, i+1, next + (char)('A' + j), allowedChars))
return true;
}
}
}
return false;
}
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
vector<vector<int>> allowedChars(7, vector<int>(7, 0));
for (const auto& s : allowed) {
allowedChars[s[0] - 'A'][s[1] - 'A'] |= 1 << (s[2] - 'A');
}
return check(bottom, 0, "", allowedChars);
}
};