756. 金字塔转换矩阵

Medium

题目描述

你正在堆叠方块来形成一个金字塔。每个方块都有一个颜色，用一个字母表示。每一行的方块数量都比下面一行少一个，并且位于下一行的中央位置。

为了使金字塔看起来美观，只允许特定的三角形图案。三角形图案由堆叠在两个方块上的单个方块组成。图案以三字母字符串列表 allowed 给出，其中图案的前两个字符分别表示左下角和右下角的方块，第三个字符是顶部方块。

例如，“ABC” 表示一个三角形图案，其中 ‘C’ 方块堆叠在 ‘A’（左）和 ‘B’（右）方块之上。注意这与 “BAC” 不同，后者中 ‘B’ 在左下角，‘A’ 在右下角。

你从底部的一行方块 bottom 开始，作为字符串给出，必须将其用作金字塔的基础。

给定 bottom 和 allowed，如果你能够一直构建到顶部，使得金字塔中的每个三角形图案都在 allowed 中，则返回 true，否则返回 false。

示例 1：

输入: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出: true
解释: 允许的三角形图案如右所示。
从底部（第3层）开始，我们可以在第2层构建"CE"，然后在第1层构建"A"。
金字塔中有三个三角形图案，分别是"BCC"、"CDE"和"CEA"。所有这些都是允许的。

示例 2：

输入: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出: false
解释: 允许的三角形图案如右所示。
从底部（第4层）开始，有多种方法构建第3层，但尝试所有可能性后，总是在构建第1层之前卡住。

提示：

2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
所有输入字符串中的字母都来自集合 {'A', 'B', 'C', 'D', 'E', 'F'}
allowed 的所有值都是唯一的

解题思路

这是一个经典的回溯问题，需要逐层构建金字塔。

核心思路：

预处理：将允许的三角形图案存储在哈希表中，以便快速查找。对于每个底边组合（如"AB"），存储所有可能的顶端字符。
回溯构建：从底层开始，逐层向上构建金字塔：
- 对于当前层，尝试每个位置的所有可能字符组合
- 使用递归回溯，当发现某种组合无法继续时，回退尝试其他组合
- 当只剩一个字符时（到达金字塔顶端），返回成功
优化策略：
- 使用记忆化避免重复计算相同的子问题
- 早期剪枝：如果某个位置没有有效的上层字符，直接返回false

算法流程：

首先构建查找表，将"AB" -> [‘C’, ‘D’] 这样的映射关系存储起来
从底层开始递归构建，每层尝试所有可能的字符组合
当到达顶层（只有一个字符）时返回true，无法构建时返回false

这种方法通过回溯和剪枝有效地探索了所有可能的构建路径。

代码实现

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> patterns;
        
        // 构建模式映射
        for (const string& pattern : allowed) {
            string key = pattern.substr(0, 2);
            patterns[key].push_back(pattern[2]);
        }
        
        return buildPyramid(bottom, patterns);
    }
    
private:
    bool buildPyramid(const string& level, unordered_map<string, vector<char>>& patterns) {
        if (level.length() == 1) {
            return true;
        }
        
        vector<string> nextLevels;
        generateNextLevel(level, 0, "", patterns, nextLevels);
        
        for (const string& nextLevel : nextLevels) {
            if (buildPyramid(nextLevel, patterns)) {
                return true;
            }
        }
        
        return false;
    }
    
    void generateNextLevel(const string& level, int pos, string current, 
                          unordered_map<string, vector<char>>& patterns, 
                          vector<string>& results) {
        if (pos == level.length() - 1) {
            results.push_back(current);
            return;
        }
        
        string key = level.substr(pos, 2);
        if (patterns.find(key) == patterns.end()) {
            return;
        }
        
        for (char c : patterns[key]) {
            generateNextLevel(level, pos + 1, current + c, patterns, results);
        }
    }
};

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        patterns = defaultdict(list)
        
        # 构建模式映射
        for pattern in allowed:
            key = pattern[:2]
            patterns[key].append(pattern[2])
        
        def build_pyramid(level):
            if len(level) == 1:
                return True
            
            next_levels = []
            generate_next_level(level, 0, "", next_levels)
            
            for next_level in next_levels:
                if build_pyramid(next_level):
                    return True
            
            return False
        
        def generate_next_level(level, pos, current, results):
            if pos == len(level) - 1:
                results.append(current)
                return
            
            key = level[pos:pos+2]
            if key not in patterns:
                return
            
            for c in patterns[key]:
                generate_next_level(level, pos + 1, current + c, results)
        
        return build_pyramid(bottom)

public class Solution {
    public bool PyramidTransition(string bottom, IList<string> allowed) {
        var patterns = new Dictionary<string, List<char>>();
        
        // 构建模式映射
        foreach (string pattern in allowed) {
            string key = pattern.Substring(0, 2);
            if (!patterns.ContainsKey(key)) {
                patterns[key] = new List<char>();
            }
            patterns[key].Add(pattern[2]);
        }
        
        return BuildPyramid(bottom, patterns);
    }
    
    private bool BuildPyramid(string level, Dictionary<string, List<char>> patterns) {
        if (level.Length == 1) {
            return true;
        }
        
        var nextLevels = new List<string>();
        GenerateNextLevel(level, 0, "", patterns, nextLevels);
        
        foreach (string nextLevel in nextLevels) {
            if (BuildPyramid(nextLevel, patterns)) {
                return true;
            }
        }
        
        return false;
    }
    
    private void GenerateNextLevel(string level, int pos, string current, 
                                  Dictionary<string, List<char>> patterns, 
                                  List<string> results) {
        if (pos == level.Length - 1) {
            results.Add(current);
            return;
        }
        
        string key = level.Substring(pos, 2);
        if (!patterns.ContainsKey(key)) {
            return;
        }
        
        foreach (char c in patterns[key]) {
            GenerateNextLevel(level, pos + 1, current + c, patterns, results);
        }
    }
}

/**
 * @param {string} bottom
 * @param {string[]} allowed
 * @return {boolean}
 */
var pyramidTransition = function(bottom, allowed) {
    const map = new Map();
    
    for (const pattern of allowed) {
        const key = pattern.slice(0, 2);
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(pattern[2]);
    }
    
    function dfs(current) {
        if (current.length === 1) {
            return true;
        }
        
        const nextLevel = [];
        
        function buildNext(index) {
            if (index === current.length - 1) {
                return dfs(nextLevel.join(''));
            }
            
            const key = current.slice(index, index + 2);
            const options = map.get(key) || [];
            
            for (const option of options) {
                nextLevel.push(option);
                if (buildNext(index + 1)) {
                    return true;
                }
                nextLevel.pop();
            }
            
            return false;
        }
        
        return buildNext(0);
    }
    
    return dfs(bottom);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(k^n) 其中 n 是底边长度，k 是平均每个位置的可能字符数。最坏情况下需要尝试所有可能的金字塔构建方式
空间复杂度	O(n + m) 其中 n 是递归调用栈的深度，m 是存储模式映射所需的空间

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析