# 756. Pyramid Transition Matrix

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like 'Z'.

For every block of color C we place not in the bottom row, we are placing it on top of a left block of color A and right block of color B. We are allowed to place the block there only if (A, B, C) 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 = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
A
/ \
D   E
/ \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
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:

1. bottom will be a string with length in range [2, 8].
2. allowed will have length in range [0, 200].
3. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

D
/ \ / \
A   B   C

class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
unordered_map<string, unordered_set<char>> m;
for (string str : allowed) {
m[str.substr(0, 2)].insert(str[2]);
}
return helper(bottom, "", m);
}
bool helper(string cur, string above, unordered_map<string, unordered_set<char>>& m) {
if (cur.size() == 2 && above.size() == 1) return true;
if (above.size() == cur.size() - 1) return helper(above, "", m);
int pos = above.size();
string base = cur.substr(pos, 2);
if (m.count(base)) {
for (char ch : m[base]) {
if (helper(cur, above + string(1, ch), m)) {
return true;
}
}
}
return false;
}
};

F _ _
D E _
A B C

class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
int n = bottom.size();
vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(7, false)));
unordered_map<char, unordered_set<string>> m;
for (string str : allowed) {
m[str[2]].insert(str.substr(0, 2));
}
for (int i = 0; i < n; ++i) {
dp[n - 1][i][bottom[i] - 'A'] = true;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
for (char ch = 'A'; ch <= 'G'; ++ch) {
if (!m.count(ch)) continue;
for (string str : m[ch]) {
if (dp[i + 1][j][str[0] - 'A'] && dp[i + 1][j + 1][str[1] - 'A']) {
dp[i][j][ch - 'A'] = true;
}
}
}
}
}
for (int i = 0; i < 7; ++i) {
if (dp[0][0][i]) return true;
}
return false;
}
};

https://leetcode.com/problems/pyramid-transition-matrix/discuss/113075/DP-O(n2-*-m)

https://leetcode.com/problems/pyramid-transition-matrix/discuss/113036/A-map-based-solution-based-on-memoization

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation