756.md

Pyramid Transition Matrix

Description

link

---

Solution

• See Code

---

Code

最坏情况：O(n^2)

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        pool=defaultdict(list)
        for x in allowed: pool[x[:2]].append(x[2])

        def dfs(bottom):
            if len(bottom)==1: return True
            for b in product(*(pool[x+y] for x,y in zip(bottom[:-1],bottom[1:]))):
                if dfs(b): return True
            return False
        
        return dfs(bottom)