金字塔转换矩阵：哈希预处理与回溯

核心结论#

每条允许规则由两个底部字符和一个顶部字符组成。先把前两个字符映射到所有可能的顶部字符，再用回溯构造上一层；只要某一层能递归到长度 1，就存在可行金字塔。

问题#

给定底层字符串 bottom 和三元组列表 allowed。规则 ABC 表示相邻方块 A、B 上方可以放置 C。需要判断能否一直构造到塔尖。

核心机制#

1. 把每条规则按前两个字符分组，例如 BCG 记录为 BC -> G。
2. 从当前层的第一个相邻字符对开始，依次尝试所有顶部候选。
3. 当新一层构造完成后，以它作为下一次递归的底层。
4. 任意字符对没有候选时立即回退。

Java 实现#

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> nextBlocks = new HashMap<>();
        for (String rule : allowed) {
            String pair = rule.substring(0, 2);
            nextBlocks.computeIfAbsent(pair, ignored -> new ArrayList<>())
                .add(rule.charAt(2));
        }
        return buildLevel(bottom, new StringBuilder(), nextBlocks);
    }

    private boolean buildLevel(
        String current,
        StringBuilder next,
        Map<String, List<Character>> nextBlocks
    ) {
        if (current.length() == 1) {
            return true;
        }
        if (next.length() == current.length() - 1) {
            return buildLevel(next.toString(), new StringBuilder(), nextBlocks);
        }

        int index = next.length();
        List<Character> candidates = nextBlocks.get(current.substring(index, index + 2));
        if (candidates == null) {
            return false;
        }

        for (char candidate : candidates) {
            next.append(candidate);
            if (buildLevel(current, next, nextBlocks)) {
                return true;
            }
            next.deleteCharAt(next.length() - 1);
        }
        return false;
    }
}

正确性与复杂度#

回溯会枚举每个相邻字符对的全部合法顶部字符，因此不会漏掉可行构造；没有映射的分支不可能继续，可安全剪枝。最坏复杂度随候选分支指数增长，但题目给定的底层长度较小。

验证#

• bottom = 'BCD'、规则包含 BCG、CDE、GEA 时应返回 true。
• 任一必要字符对没有候选时应返回 false。

参考#

• LeetCode 756：金字塔转换矩阵