Pyramid Transition Matrix
01 · Problem
You are stacking lettered blocks into a pyramid. Each row has one block fewer than the row below it, and every block rests on two adjacent blocks of the row beneath.
The string bottom is the bottom row. A block with letter T may sit on a left block L and a right block R only if the three-letter string L + R + T appears in the list allowed (first two characters are the supporting pair, left then right, and the third is the block placed on top). Each pattern may be reused any number of times.
Return true if you can build rows all the way up to a single block at the top, and false otherwise. A bottom of length 1 is already a finished pyramid.
02 · Examples
bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
true
On B,C we can place C ("BCC") and on C,D we can place E ("CDE"). The second row "CE" supports A ("CEA"), giving a single block at the top.
bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
false
Every block in the row above AAAA must be B or C. Pairs CB and CC have no pattern, and the rows reachable through BB->E and BC->D never give a pair that can support the top, so the pyramid cannot be finished.
bottom = "AB", allowed = ["ABC"]
true
The pair A,B supports C, which is the single top block.
03 · Constraints
- 01`1 <= bottom.length <= 6`
- 02`0 <= allowed.length <= 216`
- 03`allowed[i].length == 3`
- 04All letters are from the set `{'A','B','C','D','E','F'}`
- 05All strings in `allowed` are unique
04 · Optimal complexity
- Time
- O(A^n)
- Space
- O(A^n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.