I first preprocess the allowed triples to build a mapping from every valid pair of adjacent blocks (like "AB") to all possible blocks that can sit above them. This makes it easy to quickly look up what I’m allowed to place as I build the pyramid. Then I use recursion with backtracking to try to build the pyramid level by level from the given bottom row up to the top. At any point, I keep track of the current row I’m filling from and the partially-built next row. If the current row has length one, it means I successfully built all the way to the top, so I return true. If the next row is already one shorter than the current one, I recursively move up a level and start building the row above it. Otherwise, I look at the next adjacent pair in the current row, find all allowed blocks that can go above that pair, and try each one by appending it to the next row and recursing. If any recursive path reaches the top successfully, I return true; if all options fail at some point, I backtrack and eventually return false.
from collections import defaultdict
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
p_map = defaultdict(list)
for a, b, c in allowed:
p_map[a + b].append(c)
# print(p_map)
def build_rec(curr_row, next_row):
if len(curr_row) == 1:
return True
if len(next_row) == len(curr_row) - 1:
return build_rec(next_row, "")
i = len(next_row)
pair = curr_row[i:i+2]
if pair not in p_map:
return False
for ch in p_map[pair]:
if build_rec(curr_row, next_row + ch):
return True
return False
return build_rec(bottom, "")- Time: O(n^2 * a^n)
- Space: O(n^2)
