Pyramid Transition Matrix | Recursion | DP | Leetcode 756

class Solution {
    unordered_map<string,bool> memo;
    bool buildPyramid(string& bottom,string curr,int pos,int n,unordered_map<string,vector<char>>& trio){
        if(n==0)    return true;//Built Pyramid
         
        if(pos >= n){//Finished current row
            if(memo.count(curr))  return memo[curr];
            return memo[curr] = buildPyramid(curr,"",0,n-1,trio);
        }
        
        string pair = {bottom[pos],bottom[pos+1]};
        
        for(char c: trio[pair]){
            curr.push_back(c);
            if(buildPyramid(bottom,curr,pos+1,n,trio))
                return true;
            curr.pop_back();
        }
        return false;
    }
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string,vector<char>> trio;
        for(int i=0;i<allowed.size();++i)
            trio[allowed[i].substr(0,2)].push_back(allowed[i][2]);
    
        return buildPyramid(bottom,"",0,bottom.size()-1,trio);
    }
};

/*
//JAVA
import java.util.*;

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> map = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s.charAt(2));
        }
        
        return backtrack(bottom, "", map, new HashSet<>());
    }

    private boolean backtrack(String bottom, String nextRow, Map<String, List<Character>> map, Set<String> memo) {
        // Base case: pyramid completed
        if (bottom.length() == 1) return true;

        // If current row is complete, move to the next level up
        if (nextRow.length() == bottom.length() - 1) {
            if (memo.contains(nextRow)) return false;
            if (backtrack(nextRow, "", map, memo)) return true;
            memo.add(nextRow);
            return false;
        }

        // Standard backtracking to find valid blocks for the next row
        int pos = nextRow.length();
        String key = bottom.substring(pos, pos + 2);
        
        if (map.containsKey(key)) {
            for (char c : map.get(key)) {
                if (backtrack(bottom, nextRow + c, map, memo)) {
                    return true;
                }
            }
        }

        return false;
    }
}

#Python
from collections import defaultdict

class Solution:
    def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
        # Map of 'AB' -> [list of possible C's]
        adj = defaultdict(list)
        for triplet in allowed:
            adj[triplet[:2]].append(triplet[2])
            
        memo = {}

        def solve(current_layer, next_layer):
            # Base case: We've reached the top of the pyramid
            if len(current_layer) == 1:
                return True
            
            # If we finished building the current next_layer, 
            # move up to the next level
            if len(next_layer) == len(current_layer) - 1:
                state = "".join(next_layer)
                if state not in memo:
                    memo[state] = solve(next_layer, [])
                return memo[state]
            
            # Get the pair from the current base to determine the next block
            idx = len(next_layer)
            pair = current_layer[idx : idx + 2]
            
            for char in adj[pair]:
                next_layer.append(char)
                if solve(current_layer, next_layer):
                    return True
                next_layer.pop() # Backtrack
                
            return False

        return solve(list(bottom), [])
*/