# 0756. Pyramid Transition Matrix
###### tags: `Leetcode` `Medium` `Backtracking`
Link: https://leetcode.com/problems/pyramid-transition-matrix/description/
## 思路
backtracking+memo
一开始没加memo就会TLE
## Code

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> map = new HashMap<>();
        Set<String> memo = new HashSet<>();
        for(String s:allowed){
            String btm = s.substring(0,2);
            if(!map.containsKey(btm)){
                map.put(btm, new ArrayList<>());
            }
            map.get(btm).add(s.charAt(2));
        }
        return backtracking(bottom, map, memo);
    }
    private boolean backtracking(String bottom, Map<String, List<Character>> map, Set<String> memo){
        if(bottom.length()==1) return true;
        for(int i=0; i<bottom.length()-1; i++){
            if(!map.containsKey(bottom.substring(i, i+2))) return false;
        }
        List<String> list = new ArrayList<>();
        getList(bottom, map, 0, list, new StringBuilder());
        for(String s:list){
            if(memo.contains(s)) continue;
            if(backtracking(s, map, memo)) return true;
            else memo.add(s);
        }
        return false;
    }
    private void getList(String bottom, Map<String, List<Character>> map, int idx, List<String> list, StringBuilder sb){
        if(idx==bottom.length()-1){
            list.add(sb.toString());
            return;
        }
        String sub = bottom.substring(idx, idx+2);
        for(char c:map.get(sub)){
            sb.append(c);
            getList(bottom, map, idx+1, list, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}