[leetcode] 756. Pyramid Transition Matrix

[leetcode] 756. Pyramid Transition Matrix

Description

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 DWe 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’}.

分析

题目的意思是：用字母来代表每块砖的颜色，给了一个allowed数组，里面都是长度为三的字符串，比如“ABC”表示C可以放在A和B的上方，注意AB上面也可以放其他的，比如“ABD”也可以同时出现，不过搭积木的时候只能选择一种。给了一个bottom字符串，是金字塔的底层，问能不能搭出一个完整的金字塔。

首先由于想快速知道两个字母上方可以放的字母，需要建立基座字符串和上方字符集合之间的映射，由于上方字符可以不唯一，所以用个HashSet来放字符。1.1 我们的递归函数有三个参数，当前层字符串cur，上层字符串above，还有我们的HashMap。如果cur的大小为2，above的大小为1，那么说明当前已经达到金字塔的顶端了，已经搭出来了，直接返回true。1.2 否则看，如果上一层的长度比当前层的长度正好小一个，说明上一层也搭好了，我们现在去搭上上层，于是调用递归函数，将above当作当前层，空字符串为上一层，将调用的递归函数结果直接返回。1.3 否则表示我们还需要继续去搭above层，我们先算出above层的长度pos，然后从当前层的pos位置开始取两个字符，就是above层接下来需要搭的字符的基座字符。举个例子如下：

D / \ / \A B C

我们看到现在above层只有一个D，那么pos为1，在cur层1位置开始取两个字符，得到"BC"，即是D的下一个位置的字符的基座字符串base。取出了base后，如果HashMap中有映射，则我们遍历其映射的字符集合中的所有字符，对每个字符都调用递归函数，此时above字符串需要加上这个遍历到的字符，因为我们在尝试填充这个位置，如果有返回true的，那么当前递归函数就返回true了，否则最终返回false，

代码

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

参考文献

​​[LeetCode] Pyramid Transition Matrix 金字塔转变矩阵​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。