Pyramid Transition Matrix — LeetCode 756 Python Solution

The problem

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter.

Example

Input

bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]

Output

true

Explanation

The allowed triangular patterns are shown on the right.

Python solution

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        @cache
        def dfs(s: str) -> bool:
            if len(s) == 1:
                return True
            t = []
            for a, b in pairwise(s):
                cs = d[a, b]
                if not cs:
                    return False
                t.append(cs)
            return any(dfs("".join(nxt)) for nxt in product(*t))

        d = defaultdict(list)
        for a, b, c in allowed:
            d[a, b].append(c)
        return dfs(bottom)

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 756. Pyramid Transition Matrix is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems