Colored Block Pyramid

Medium

You are building a pyramid of blocks, each colored with an uppercase Latin letter. Every row is one block shorter than the row below it, and each of its blocks rests on exactly two neighbouring blocks underneath. The color combinations are restricted by a list of patterns. A pattern is a three-letter string: the first two letters are the left and right blocks below, the third is the block that may be placed on top of them. For example, "ABC" lets you put C on the pair (A on the left, B on the right), but not on the pair (B on the left, A on the right). The bottom row is given by the string base. Return True if the pyramid can be completed up to a single top block with every "two below, one on top" triple appearing in patterns, and False otherwise.

Example 1

base="ACE", patterns=["ACB", "CED", "BDF"] → True

B goes on top of AC and D on top of CE, giving the row BD. F goes on top of BD and the pyramid is complete.

Example 2

base="ABA", patterns=["ABC", "BAD", "DCE"] → False

The only possible second row is CD, and there is no pattern for the pair CD (only for DC, and order matters). The pyramid cannot be finished.

Example 3

base="FF", patterns=[] → False

Constraints

2 ≤ len(base) ≤ 6
0 ≤ len(patterns) ≤ 216
Each pattern is a string of length 3 (patterns may repeat)
All letters are uppercase Latin letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Depth-First Search Breadth-First Search