You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains one less block than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific triangular patterns that are allowed. A triangular pattern consists of a single block stacked on top of two blocks. The patterns are given&nbsp;as a list of&nbsp;three-letter strings allowed, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.


	For example, "ABC" represents a triangular pattern with a 'C' block stacked on top of an 'A' (left) and 'B' (right) block. Note that this is different from "BAC" where 'B' is on the left bottom and 'A' is on the right bottom.


You start with a bottom row of blocks bottom, given as a single string, that you must use as the base of the pyramid.

Given bottom and allowed, return true if you can build the pyramid all the way to the top such that every triangular pattern in the pyramid is in allowed, or false otherwise.

&nbsp;
Example 1:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true
Explanation: The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.
There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.


Example 2:

Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
Output: false
Explanation: The allowed triangular patterns are shown on the right.
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.


&nbsp;
Constraints:


	2 &lt;= bottom.length &lt;= 6
	0 &lt;= allowed.length &lt;= 216
	allowed[i].length == 3
	The letters in all input strings are from the set {'A', 'B', 'C', 'D', 'E', 'F'}.
	All the values of allowed are unique.


class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool    
        """
        dic = defaultdict(list)
        for i in allowed:
            dic[(i[0], i[1])].append(i[2])
        
        res = []
        
        def dfs(arr, nxt):
            #base case second floor and check top exists
            if len(arr) == 2 and dic[(arr[0], arr[1])]:
                return True
            
            #go to the next row now
            if len(arr) == len(nxt) + 1:
                return dfs(nxt, [])

            #keep iterating the same row
            if dic[(arr[len(nxt)], arr[len(nxt) + 1])]:
                for val in dic[(arr[len(nxt)], arr[len(nxt) + 1])]:
                    if dfs(arr, nxt + [val]):
                        return True
            return False
        
        return dfs(bottom, [])
class Solution {
    HashMap<String, List<Character>> map = new HashMap<>();
    HashMap<String, Boolean> dp = new HashMap<>();
    
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        for(String s:allowed){
            String sub = s.substring(0,2);
            
            char c = s.charAt(2);
            
            if(!map.containsKey(sub))
                map.put(sub, new ArrayList<>());
            
            map.get(sub).add(c);
        }
        
        return dfs(bottom, "", 0);
    }
    
    boolean dfs(String currBottom, String newBottom, int index){
        
        if(currBottom.length()==1)
            return true;
        if(index+1>=currBottom.length())
            return false;
        
        String sub = currBottom.substring(index,index+2);
        
        String state = currBottom+" "+newBottom+" "+index;
        
        if(dp.containsKey(state))
            return dp.get(state);
        
        if(map.containsKey(sub)){
            List<Character> letters = map.get(sub);
            
            for(char c:letters){
                if(index==currBottom.length()-2){
                    if(dfs(newBottom+c, "", 0))
                    {
                        dp.put(state, true);
                        return true;
                    }
                }
                else if(dfs(currBottom, newBottom+c, index+1))
                {
                    dp.put(state, true);
                    return true;
                }
            }
        }
        
        dp.put(state, false);
        return false;
    }
}
class Solution {
    unordered_map<string,vector<char> > m;
public:
    bool dfs(string bot,int i,string tem){
        if(bot.size()==1) return true;
        if(i==bot.size()-1) {
            string st;
            return dfs(tem,0,st);
        }
        for(auto v:m[bot.substr(i,2)]){
            tem.push_back(v);
            if(dfs(bot,i+1,tem)){
                return true;
            }
            tem.pop_back();
        }
        return false;
    }
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for(auto a:allowed){
            m[a.substr(0,2)].push_back(a[2]);
        }
        string te;
        return dfs(bottom,0,te);
    }
};
var pyramidTransition = function(bottom, allowed) {
    const set = new Set(allowed);
    const memo = new Map();
    const chars = ["A", "B", "C", "D", "E", "F"];
    
    return topDown(bottom, bottom.length - 1);
    
    function topDown(prev, row) {
        const key = `${prev}#${row}`;
        
        if (row === 0) return true;
        if (memo.has(key)) return memo.get(key);

        let pats = new Set();
        pats.add("");

        for (let i = 0; i < row; i++) {
            const tmp = new Set();

            const leftBot = prev.charAt(i);
            const rightBot = prev.charAt(i + 1);

            for (const char of chars) {
                const triadStr = leftBot + rightBot + char;

                if (set.has(triadStr)) {
                    for (const pat of pats) {
                        tmp.add(pat + char);
                    }                 
                }
            }
          
            pats = tmp;
        }
        
        for (const pat of pats) {
            if (topDown(pat, row - 1)) return true;
        }
        
        memo.set(key, false);
        return false;
    }
};
Pyramid Transition Matrix