image.png
问题描述
我们将砖块堆成一个金字塔。每块砖有一种颜色，用一个字母表示。
只有当 ABC 是允许的三角形时，我们可以把任意颜色的 C 放到 AB 上。
我们将字符串 bottom 作为底部砖块开始，allowed 数组表示允许创建的三角形，每个元素是长度为 3 的字符串。
如果我们可以构建到金字塔的顶部，则返回 true，否则返回 false。
栗 1：
输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出：true
解释：
可以构建如下金字塔：
A
/ \
G E
/ \ / \
B C D
栗 2：
输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：false
解释：
无法构建完成。因为 BA 上只能放 C，而没有满足 "XCX" 的三角形。
注意：
-
bottom是一个字符串，长度范围在[2, 8]。 -
allowed长度范围在[0, 200]。 - 字符串中每个字母的取值都在
{'A', 'B', 'C', 'D', 'E', 'F', 'G'}中。
解题思路
思路倒是不难，但是代码实现对我来说却有些困难。但看过代码之后又觉得很简单，看易行难。
由于是金字塔形状，每层砖块的数量是以一逐渐递减的。若能堆成，则最顶部只有一个砖块。
上一层的砖块取值基于下一层来计算。因为可允许的三角形可能有多个，对于每两个相邻的砖块来说，可堆在它上面的砖块也会有多种选择。这样的话，我们需要遍历每层多种组合的情况，再一层层往上依次判断，只要有一种情况可堆到顶部，就视为可行。
所以呢，得遍历每层的 N 种组合，使用穷举的方式来判断。
单看文字可能不太容易理解。一图胜千言，请看下图。
image.png
简单解释一下：
- 在最后一层中的砖块为
ABCD。假设AB可能的结果为[C,D]，BC可能的结果为[E,F]，CD可能的结果为[A]。 - 在倒数第二层，依次计算两个相邻砖块的可能取值。当
[C,D]与[E,F]两两组合后，根据allowed数组 ，假设可能的结果为[A,D]; 同样[E,F]分别于[A]进行组合，可能的结果为[B,D]。 - ...，以此类推，看是否能一直到顶。
通过这个例子，我们会很自然的想到记录下 allowed 中前两个字符与第三个字符所有的对应情况，以便于后续查询。
但如何得到每一层的所有组合情况呢？我们可以这样考虑。
拿最后一层举例，看看计算倒数第二层的组合情况。
- 当处理
AB时，对应的结果有[C,D]。这时候，我们需要逐个遍历[C,D]中的元素，把它作为倒数第二层的第一块砖。 - 接着，处理
BC，它的结果对应[E,F]。同样，遍历数组中的每个元素，将其作为第二块砖。 - 最后，处理
CD， 它的结果对应[A]，同样进行遍历，将其作为第三块砖。
这样，倒数第二层中所有可能的组合就可计算出了，每种组合包含三个砖块。
倒数第三层类似，不再赘述。
那么最终可行的判定条件是什么？很简单，当某层的砖块数量为 1 时，即喜登金顶。
由于我们是从下往上一层一层的计算，需要考虑到什么时候会换层。即当遍历到底部的最后一块砖时，便切换到下一层。
具体实现可以重点看下 dfs 函数，比文字描述更加清晰。
代码如下：
var pyramidTransition = function (bottom, allowed) {
// 记录前两个字符与第三个字符的对应情况。{"AB":['x','x']}
let allowMap = new Map();
allowed.forEach((element) => {
// 取前 2 位
const prefix = element.slice(0, 2);
const value = element[2];
let list;
if (allowMap.has(prefix)) {
list = allowMap.get(prefix);
} else {
list = new Array();
}
list.push(value);
allowMap.set(prefix, list);
});
// 递归
return dfs(bottom, 0, "", allowMap);
};
// 递归计算
var dfs = function (bottom, i, str, map) {
// 满足条件
if (bottom.length === 1) {
return true;
}
// 当前层的最后一个，需换到下一层
if (i === bottom.length - 1) {
return dfs(str, 0, "", map);
}
// 取前两块
const prefix = bottom.slice(i, i + 2);
if (map.has(prefix)) {
const list = map.get(prefix);
let j = 0;
// 遍历每种可能的值
while (j < list.length) {
const b = list[j];
// 找下一个块
if (dfs(bottom, i + 1, str + b, map)) {
return true;
}
j += 1;
}
}
return false;
};
网友评论