LC_756_PyramidTransitionMatrix

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        int n = allowed.size();
        
        Map<String, List<Character>> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            String str = allowed.get(i);
            String key = str.substring(0,2);
            if(map.containsKey(key)){
                map.get(key).add(str.charAt(2));
            }
            else{
                List<Character> newList = new ArrayList<>();
                newList.add(str.charAt(2));
                map.put(key,newList);
            }
        }
        return makeLayer(bottom, map);
    } 

    public boolean makeLayer(String bottom, Map<String, List<Character>> map) {
        if(bottom.length() == 1) return true;
        return build(bottom, 0, map, new StringBuilder());
    }

    public boolean build(String bottom, int i, Map<String, List<Character>> map, StringBuilder str){
        if(i >= bottom.length()-1){
            return makeLayer(str.toString(), map);
        }
        String test = bottom.substring(i, i+2);
        if(!map.containsKey(test)) return false;

        for(char ch : map.get(test)){
            str.append(ch);
            if(build(bottom, i+1, map,str)) return true;
            str.deleteCharAt(str.length()-1);
        }
        return false;
    }
}