# 756 Pyramid Transition Matrix

## 756. [Pyramid Transition Matrix](https://leetcode.com/problems/pyramid-transition-matrix/description/)

## 1. Question

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like \`'Z'\`.

For every block of color \`C\` we place not in the bottom row, we are placing it on top of a left block of color \`A\` and right block of color \`B\`. We are allowed to place the block there only if \`(A, B, C)\` is an allowed triple.

We start with a bottom row of`bottom`, represented as a single string. We also start with a list of allowed triples`allowed`. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

**Example 1:**

```
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]

Output: true

Explanation:

We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.
```

**Example 2:**

```
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]

Output: false

Explanation:

We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
```

**Note:**

1. `bottom`will be a string with length in range`[2, 8]`.
2. `allowed`will have length in range`[0, 200]`.
3. Letters in all strings will be chosen from the set`{'A', 'B', 'C', 'D', 'E', 'F', 'G'}`.

## 2. Implementation

(1) DFS + HashMap

思路:

(1) 根据题意，从bottom level根据allowed的string搭建金字塔，由于上一层里能放的character都要根据下一层的两个character决定，所以我们首先通过HashMap建立allowed string前两个character和最后一个character的映射关系

(2) 第二步就是通过DFS搭建金字塔，递归函数的参数定义分别是curLevel代表当前一层，lastLevel代表上一层，map则是第一步构造的HashMap. 如果当前一层的size为2，上一层的size为1，说明我们已经到塔顶，return true. 如果上一层的size比当前层少1，说明上一层已经搭好，我们要搭上上一层。在搭建上一层的过程中，我们先取到上一层待搭建的位置index，然后根据这个index在当前层中通过hashmap找到可以放置的character，递归实现

```java
class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, Set<Character>> map = new HashMap<>();

        for (String s : allowed) {
            String key = s.substring(0, 2);
            if (!map.containsKey(key)) {
                map.put(key, new HashSet<>());
            }
            map.get(key).add(s.charAt(2));
        }
        return canReachTop(bottom, "", map);
    }

    public boolean canReachTop(String curLevel, String lastLevel, Map<String, Set<Character>> map) {
        if (curLevel.length() == 2 && lastLevel.length() == 1) {
            return true;
        }

        if (lastLevel.length() == curLevel.length() - 1) {
            return canReachTop(lastLevel, "", map);
        }

        int index = lastLevel.length();
        String key = curLevel.substring(index, index + 2);

        if (map.containsKey(key)) {
            for (char c : map.get(key)) {
                if (canReachTop(curLevel, lastLevel + c, map)) {
                    return true;
                }
            }
        }
        return false;
    }

}
```

## 3. Time & Space Complexity

时间复杂度O(n^2 + m),n是bottom的长度，从底层到顶层需要的character个数为n + (n - 1) + (n - 2) +... + 1=>O(n^2), m是allowed string的个数，构建hashMap需要O(m)的长度， 空间复杂度O(m + n^2), 递归深度是n^2, hashMap空间复杂度是O(m)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/756-pyramid-transition-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.