> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Pyramid Transition Matrix Python Solution

> Tested Python solution for LeetCode 756 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 756, [Medium](/catalog/medium). Topics: [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation). [View on LeetCode](https://leetcode.com/problems/pyramid-transition/description/).

Generate this problem as a practice environment: tested reference solution, 21 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 756   # by problem number
lcpy gen -s pyramid_transition   # by problem name
```

## Problem

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains **one less block** than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific **triangular patterns** that are allowed. A triangular pattern consists of a **single block** stacked on top of **two blocks**. The patterns are given as a list of three-letter strings `allowed`, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

* For example, `"ABC"` represents a triangular pattern with a `'C'` block stacked on top of an `'A'` (left) and `'B'` (right) block. Note that this is different from `"BAC"` where `'B'` is on the left bottom and `'A'` is on the right bottom.

You start with a bottom row of blocks `bottom`, given as a single string, that you **must** use as the base of the pyramid.

Given `bottom` and `allowed`, return `true` if you can build the pyramid all the way to the top such that **every triangular pattern** in the pyramid is in `allowed`, or `false` otherwise.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/08/26/pyramid1-grid.jpg)

```
Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true
```

**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.
There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.

![Example 2](https://assets.leetcode.com/uploads/2021/08/26/pyramid2-grid.jpg)

```
Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
Output: false
```

**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

### Constraints

* `2 <= bottom.length <= 6`
* `0 <= allowed.length <= 216`
* `allowed[i].length == 3`
* The letters in all input strings are from the set `{'A', 'B', 'C', 'D', 'E', 'F'}`.
* All the values of `allowed` are **unique**.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/pyramid_transition/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/pyramid_transition/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from itertools import product


class Solution:
    # Time: O(k^(n-1)) states memoized by row; n <= 6 so bounded by 6^5 rows
    # Space: O(k^(n-1)) for the memo set of dead rows
    def pyramid_transition(self, bottom: str, allowed: list[str]) -> bool:
        tops: dict[str, list[str]] = {}
        for pattern in allowed:
            tops.setdefault(pattern[:2], []).append(pattern[2])

        dead: set[str] = set()

        def dfs(row: str) -> bool:
            if len(row) == 1:
                return True
            if row in dead:
                return False
            dead.add(row)
            options = [tops.get(row[i : i + 2], ()) for i in range(len(row) - 1)]
            return any(dfs("".join(level)) for level in product(*options))

        return dfs(bottom)
```

## Complexity

| Time | Space |
| - | - |
| O(k^(n-1)) states memoized by row; n \<= 6 so bounded by 6^5 rows | O(k^(n-1)) for the memo set of dead rows |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.