756.金字塔转换矩阵：深度优先搜索

【LetMeFly】756.金字塔转换矩阵：深度优先搜索

力扣题目链接：https://leetcode.cn/problems/pyramid-transition-matrix/

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块 ，并且居中。

为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 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 层构建“E”。
金字塔中有三种三角形图案，分别是 “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 中所有值都是 唯一的

解题方法：深度优先搜索

    A
  B   C
D   E   F

上面金字塔可以写成下面的样子：

A
B C
D E F

这样就可以使用二维数组来表示了（二维数组变量名设为pyramid）。

按什么顺序填充呢？已知题目给定了bottom，那就由下往上由左往右地填充呗！

写一个dfs函数接收两个参数，dfs(int i, int j)代表填充到二维数组pyramid[i][j]时，整个金字塔是否有解。

如何填充？把所有可以填充的方案依次尝试一下：

bool dfs(int i, int j) {
    for (char c : canFill(pyramid[i+1][j], pyramid[i+1][j+1])) {
        pyramid[i][j] = c;
        if (dfs(i, j + 1)) {  // 下一步：填充右边一格
            return true;
        }
    }
    return false;
}

其中canFill可以是一个map，快速通过底层两个元素映射到所有上层可以填充的元素。

终止条件？首先递归逻辑是接下来填充右边一格，如果这一行填充完了则改为填充上一行：

bool dfs(int i, int j) {
    if (j > i) {
        return dfs(i - 1, 0);
    }
}

如果第一行（i=0）也填满了，就会递归到i=-1行，此时也说明整个金字塔已经填充完毕了，返回true。

• 时间复杂度$O(|\sum|^{n^2})$，其中$n=len(bottom)$而$|\sum|$代表字母集合的大小$6$，搜索树的高度为i*j共计$n^2$，每个节点至多$|\sum|$个儿子。
• 空间复杂度$O(m+n^2)$，其中$m=len(allowed)$

AC代码

C++

/*
 * @LastEditTime: 2025-12-29 22:37:18
 */
class Solution {
private:

    vector<char> mappings[36];
    vector<vector<char>> pyramid;

    inline int bottom2int(char a, char b) {
        return (a - 'A') * 6 + b - 'A';
    }

    bool dfs(int i, int j) {
        if (i < 0) {
            return true;
        }
        if (j > i) {
            return dfs(i - 1, 0);
        }

        for (char c : mappings[bottom2int(pyramid[i + 1][j], pyramid[i + 1][j + 1])]) {
            pyramid[i][j] = c;
            if (dfs(i, j + 1)) {
                return true;
            }
        }
        return false;
    }

public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (string& s : allowed) {
            mappings[bottom2int(s[0], s[1])].push_back(s[2]);
        }
        int n = bottom.size();
        pyramid.resize(n);
        for (int i = 0; i < n; i++) {
            pyramid[i].resize(i + 1);
        }
        for (int i = 0; i < n; i++) {
            pyramid[n - 1][i] = bottom[i];
        }
        return dfs(n - 2, 0);
    }
};

End

今日黄金仍在持续下跌中~ 每盎司单日跌超200美元了

The Real End, Thanks!

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源