756. Pyramid Transition Matrix


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'}.


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

Intuition and Algorithm

We model the states that blocks can be in. Each state is a binary number where the kth bit is set if the kth 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

  • Time Complexity: , where is the length of bottom, is the length of allowed, and is the size of the alphabet.

  • Space Complexity: in additional space complexity.

Approach #2: Depth-First Search [Accepted]

Intuition

We exhaustively try every combination of blocks.

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

  • Time Complexity: , where is the length of 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 .

  • Space Complexity: additional space complexity.

Analysis written by: @awice.

Submit Solution