Problem statement

https://leetcode.com/problems/pyramid-transition-matrix/

Solution

The idea is to use classical dfs, where we given state we crate all possible combinations for next layer: for each pair of adjacent letters we check what options we have.

Complexity

Time complexity is O(A^n), where n is length of bottom and A is the size of alphabet.

Code

class Solution:
    def pyramidTransition(self, bottom, allowed):
        d = defaultdict(set)
        for a, b, c in allowed:
            d[a, b].add(c)

        def dfs(bottom):
            if (k := len(bottom)) == 1: return True
            for state in product(*(d[bottom[i], bottom[i+1]] for i in range(k-1))):
                if dfs(state): return True
            return False
        
        return dfs(bottom)

Remark

I also tried bfs, but it gets you TLE in this problem, be careful! Even though theoretical complexity is the same, in practice dfs will find solutions much faster on given tests.