[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   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:

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

分析

題目的意思是：用字母來代表每塊磚的顔色，給了一個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      

代碼

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string,unordered_set<char>> 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<string,unordered_set<char>>& 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;
    }
};      

參考文獻