#756

Pyramid Transition Matrix

specialist · 750 · lc medium +31 · verified · 60.6% accepted · 960 likes · top 59%

Description

Build a pyramid of colored blocks where each row is one block shorter than the row below. Each three-block triangle (left, right, top) must match one of the allowed patterns given as three-character strings in allowed (first char = left block, second = right block, third = block placed on top).

Given the mandatory bottom row and the allowed patterns, return true if a valid pyramid can be constructed all the way to a single top block, otherwise false.

Example 1:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]

Output: true

Explanation: The allowed triangular patterns are shown on the right.

Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.

There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.

Example 2:

Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]

Output: false

Explanation: The allowed triangular patterns are shown on the right.

Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

Code

1

2

3

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool: