leetcode [756] 金字塔转换矩阵

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。

使用三元组表示金字塔的堆砌规则如下：

对于三元组(A, B, C) ，“C”为顶层方块，方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组，我们才可以将其堆砌上。

初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。

如果可以由基层一直堆到塔尖就返回 true，否则返回 false。

示例 1:

输入: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出: true
解析:
可以堆砌成这样的金字塔:
    A
   / \
  G   E
 / \ / \
B   C   D

因为符合('B', 'C', 'G'), ('C', 'D', 'E') 和 ('G', 'E', 'A') 三种规则。

示例 2:

输入: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出: false
解析:
无法一直堆到塔尖。
注意, 允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组，其中 C != D。

注意：

1. bottom 的长度范围在 [2, 8]。
2. allowed 的长度范围在[0, 200]。
3. 方块的标记字母范围为{'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

来自题解:

先根据allowed生成前缀树，然后检查bottom生成上一层的候选。主要的困难在于生成候选的笛卡尔积，这里使用python的product。

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        from itertools import product
        from collections import defaultdict
        f = defaultdict(lambda: defaultdict(list))
        for a, b, c in allowed:
            f[a][b].append(c)
        
        def pyramid(inner_bottom):
            if len(inner_bottom) == 1:
                return True
            for i in product(*(f[a][b] for a, b in zip(inner_bottom, inner_bottom[1:]))):
                if pyramid(i):
                    return True
            return False
        
        return pyramid(bottom)