# 756. Pyramid Transition Matrix 金字塔转换矩阵

@TOC

## # 题目描述

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'}.

## # 解题方法

### # 回溯法

``````class Solution(object):
def pyramidTransition(self, bottom, allowed):
"""
:type bottom: str
:type allowed: List[str]
:rtype: bool
"""
m = collections.defaultdict(list)
for triples in allowed:
m[triples[:2]].append(triples[-1])
return self.helper(bottom, "", m)

def helper(self, curr, above, m):
if len(curr) == 2 and len(above) == 1:
return True
if len(above) == len(curr) - 1:
return self.helper(above, "", m)
pos = len(above)
base = curr[pos : pos+2]
if base in m:
for ch in m[base]:
if self.helper(curr, above + ch, m):
return True
return False
``````

C++代码如下：

``````class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
if (bottom.size() == 1) return true;
for (string& a : allowed) {
m_[a.substr(0, 2)].push_back(a[2]);
}
return helper(bottom, "", m_);
}
private:
unordered_map<string, vector<char>> m_;
bool helper(string pre, string cur, unordered_map<string, vector<char>>& m_) {
if (pre.size() == 2 && cur.size() == 1) return true;
if (pre.size() - cur.size() == 1)
return helper(cur, "", m_);
int pos = cur.size();
string next = pre.substr(pos, 2);
for (char cs : m_[next]) {
if (helper(pre, cur + cs, m_)) {
return true;
}
}
return false;
}
};
``````

http://www.cnblogs.com/grandyang/p/8476646.html

## # 日期

2018 年 9 月 6 日 —— 作息逐渐规律。 2019 年 1 月 25 日 —— 这学期最后一个工作日