This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:trueExplanation: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:falseExplanation: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:**

`bottom`

will be a string with length in range`[2, 8]`

.`allowed`

will have length in range`[0, 200]`

.- Letters in all strings will be chosen from the set
`{'A', 'B', 'C', 'D', 'E', 'F', 'G'}`

.

b'

\n#### Approach #1: State to State Transition [Wrong Answer]

\n

\n#### Approach #2: Depth-First Search [Accepted]

\n

\n

'
\n\n

\n**Intuition and Algorithm**

We model the states that blocks can be in. Each state is a binary number where the `k`

th bit is set if the `k`

th type of block is a possibility. Then, we create a transition map `T[state1][state2] -> state`

that takes a left state and a right state and outputs all possible parent states.

At the end, applying these transitions is straightforward. However, this approach is not correct, because the transitions are not independent. If for example we have states in a row `A, {B or C}, A`

, and allowed triples `(A, B, D)`

, `(C, A, D)`

, then regardless of the choice of `{B or C}`

we cannot create the next row of the pyramid.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`bottom`

, is the length of`allowed`

, and is the size of the alphabet. \n - \n
Space Complexity: in additional space complexity.

\n \n

\n

**Intuition**

We exhaustively try every combination of blocks.

\n**Algorithm**

We can work in either strings or integers, but we need to create a transition map `T`

from the list of allowed triples. This map `T[x][y] = {set of z}`

will be all possible parent blocks for a left child of `x`

and a right child of `y`

. When we work in strings, we use `Set`

, and when we work in integers, we will use the set bits of the result integer.

Afterwards, to `solve`

a row, we generate every possible combination of the next row and solve them. If any of those new rows are solvable, we return `True`

, otherwise `False`

.

We can also cache intermediate results, saving us time. This is illustrated in the comments for Python. For Java, all caching is done with lines of code that mention the integer `R`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`bottom`

, and is the size of the alphabet, and assuming we cache intermediate results. We might try every sequence of letters for each row. [The total complexity is because is a geometric series equal to .] Without intermediate caching, this would be . \n - \n
Space Complexity: additional space complexity.

\n \n

\n

Analysis written by: @awice.

\n