# LeetCode 756: Pyramid Transition Matrix

## Problem Restatement

We are given a bottom row of blocks.

Each block has a color represented by one letter.

We are also given a list of allowed triples. A triple has length `3`.

For example:

```python
"ABC"
```

means:

```text
A B
 C
```

If two adjacent blocks are `A` and `B`, then we may place `C` on top of them.

Starting from the given `bottom` row, we need to decide whether it is possible to build the pyramid all the way to one block at the top.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `bottom`, the starting bottom row |
| Input | `allowed`, a list of allowed triples |
| Output | `True` if the pyramid can be built, otherwise `False` |
| Rule | A block can be placed above two adjacent blocks only if the triple is allowed |

Example function shape:

```python
def pyramidTransition(bottom: str, allowed: list[str]) -> bool:
    ...
```

## Examples

Example 1:

```python
bottom = "BCD"
allowed = ["BCG", "CDE", "GEA", "FFF"]
```

Output:

```python
True
```

We can build:

```text
  A
 G E
B C D
```

The pair `"BC"` can produce `"G"` because `"BCG"` is allowed.

The pair `"CD"` can produce `"E"` because `"CDE"` is allowed.

Then the pair `"GE"` can produce `"A"` because `"GEA"` is allowed.

So the pyramid can reach the top.

Example 2:

```python
bottom = "AABA"
allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
```

Output:

```python
False
```

There is no way to choose blocks above each row so that the pyramid reaches a single top block.

## First Thought: Try All Possible Rows

Each row depends on the row below it.

For a row like:

```text
AABA
```

we need to build a row of length `3`.

The adjacent pairs are:

```text
AA
AB
BA
```

For each pair, there may be zero, one, or many possible top blocks.

So we need to try all combinations for the next row.

After building one possible next row, we repeat the same process until the row length becomes `1`.

This is a natural backtracking problem.

## Key Insight

Instead of thinking about the whole pyramid at once, ask this smaller question:

Given the current row, can we build a valid pyramid above it?

If the row has length `1`, the answer is `True`.

Otherwise, we generate every possible row above the current row. If any generated row can reach the top, the current row is also possible.

This gives a recursive solution.

## Preprocessing Allowed Triples

We should not scan the full `allowed` list every time we see a pair.

Instead, build a map from each bottom pair to all possible top blocks.

For example:

```python
allowed = ["BCG", "BCD", "CDE"]
```

Then the map is:

```python
{
    "BC": ["G", "D"],
    "CD": ["E"],
}
```

Code:

```python
from collections import defaultdict

top_blocks = defaultdict(list)

for triple in allowed:
    pair = triple[:2]
    top = triple[2]
    top_blocks[pair].append(top)
```

Now we can quickly answer:

```text
What blocks can go above this pair?
```

## Generating the Next Row

Suppose the current row is:

```python
row = "AABA"
```

We need one block above each adjacent pair.

The pairs are:

```text
AA, AB, BA
```

If:

```python
AA -> ["A", "B"]
AB -> ["A", "B"]
BA -> ["C"]
```

then possible next rows include:

```text
AAC
ABC
BAC
BBC
```

We can generate these rows with DFS.

There are two levels of recursion:

1. Build one next row from left to right.
2. Recursively check whether that next row can reach the top.

## Algorithm

1. Build a dictionary `top_blocks`:
   1. key: two-letter bottom pair
   2. value: list of possible top letters
2. Define `can_build(row)`:
   1. If `len(row) == 1`, return `True`.
   2. Generate every possible row above `row`.
   3. If any generated row satisfies `can_build(next_row)`, return `True`.
   4. Otherwise return `False`.
3. Use memoization so the same row is not solved repeatedly.
4. Return `can_build(bottom)`.

## Correctness

The dictionary `top_blocks` stores exactly the allowed moves from each adjacent pair to a possible upper block.

For any row of length greater than `1`, a valid next row must choose one allowed top block for every adjacent pair in that row. The generation step tries every such choice. Therefore, it produces exactly all valid rows that can be placed directly above the current row.

The recursive function returns `True` for a row of length `1`, because a one-block row is already the top of a complete pyramid.

For a longer row, the function returns `True` if at least one valid next row can itself reach the top. This matches the definition of being able to build a pyramid above the current row.

If no generated next row can reach the top, then every possible immediate choice fails, so no valid pyramid exists from that row.

By induction on row length, `can_build(row)` returns `True` exactly when a valid pyramid can be built above `row`. Therefore, `can_build(bottom)` gives the correct answer.

## Complexity

Let `m = len(bottom)`.

The maximum row length is at most `8`, and letters come from a small fixed set. In the worst case, many possible rows may be generated.

| Metric | Value | Why |
|---|---|---|
| Time | Exponential in `m` | Many combinations of upper rows may need to be tried |
| Space | Exponential in `m` | Memoization may store many reachable row states |

With the problem constraints, DFS with memoization is efficient enough.

## Implementation

```python
from collections import defaultdict
from functools import lru_cache

class Solution:
    def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
        top_blocks = defaultdict(list)

        for triple in allowed:
            pair = triple[:2]
            top = triple[2]
            top_blocks[pair].append(top)

        @lru_cache(None)
        def can_build(row: str) -> bool:
            if len(row) == 1:
                return True

            candidates = []

            def build_next(index: int, path: list[str]) -> bool:
                if index == len(row) - 1:
                    next_row = "".join(path)
                    return can_build(next_row)

                pair = row[index:index + 2]

                if pair not in top_blocks:
                    return False

                for top in top_blocks[pair]:
                    path.append(top)

                    if build_next(index + 1, path):
                        return True

                    path.pop()

                return False

            return build_next(0, [])

        return can_build(bottom)
```

## Code Explanation

We first group allowed triples by their bottom pair:

```python
top_blocks = defaultdict(list)

for triple in allowed:
    pair = triple[:2]
    top = triple[2]
    top_blocks[pair].append(top)
```

If `triple = "BCG"`, then:

```python
pair = "BC"
top = "G"
```

So `"G"` is one possible block above `"BC"`.

The main recursive function is:

```python
@lru_cache(None)
def can_build(row: str) -> bool:
```

It answers whether a full pyramid can be built from `row`.

The base case is:

```python
if len(row) == 1:
    return True
```

A single block means the pyramid is complete.

Inside `can_build`, we define another helper:

```python
def build_next(index: int, path: list[str]) -> bool:
```

This helper builds the next row one character at a time.

The variable `index` tells us which adjacent pair in `row` we are processing.

The list `path` stores the partial next row.

When `index == len(row) - 1`, we have placed one block above every adjacent pair:

```python
next_row = "".join(path)
return can_build(next_row)
```

If a pair has no possible top block, this path cannot work:

```python
if pair not in top_blocks:
    return False
```

Otherwise, we try every allowed top block:

```python
for top in top_blocks[pair]:
    path.append(top)

    if build_next(index + 1, path):
        return True

    path.pop()
```

If any choice succeeds, we immediately return `True`.

If every choice fails, we return `False`.

The final answer is:

```python
return can_build(bottom)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.pyramidTransition(
        "BCD",
        ["BCG", "CDE", "GEA", "FFF"],
    ) is True

    assert s.pyramidTransition(
        "AABA",
        ["AAA", "AAB", "ABA", "ABB", "BAC"],
    ) is False

    assert s.pyramidTransition(
        "AA",
        ["AAB"],
    ) is True

    assert s.pyramidTransition(
        "AA",
        [],
    ) is False

    assert s.pyramidTransition(
        "ABC",
        ["ABD", "BCE", "DEF"],
    ) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"BCD"` example | Confirms a valid pyramid is found |
| `"AABA"` example | Confirms impossible case |
| Two-block bottom with one allowed triple | Simplest successful construction |
| Two-block bottom with no allowed triples | Simplest failure |
| Multi-level construction | Confirms recursion moves upward correctly |