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.