題目描述

現在，我們用一些方塊來堆砌一個金字塔。 每個方塊用僅包含一個字母的字符串表示。

使用三元組表示金字塔的堆砌規則如下：

對于三元組(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。

這個題個人感覺難度應該不算中等 屬于看題解看半天都不是很懂的那種，可能我太菜了QAQ 最開始看著示例結構 想用創建赫夫曼樹的方法試一下忽略了最重要的一點一個子節點可以擁有多個父節點 所以才想到用dfs遍歷每一種可能的情況 代碼和思路如下：

// 思路：

// 判斷是否可以堆砌成金字塔取決于是否可以達到塔頂只有一個數組

// 注意1：可能存在兩個字母可以組合成多種字母的情況 所以考慮用Map映射來保存規則

// 注意2: 和二叉樹不同 一個節點可能有兩個父節點，排除赫夫曼樹做法

class Solution {

public boolean pyramidTransition(String bottom, List allowed) {

if(allowed.size() == 0) return false;

Map> map = getMap(allowed);

// System.out.println(map);

return dfs(map, bottom, "");

}

/*參數說明

*map 映射表

*boom 當前構建層的基層

*up 構建層

*/

public boolean dfs(Map> map, String boom, String up) {

if(up.length() == 1 && boom.length() == 2) return true; // 完成最后一層構建

if(up.length() ==? boom.length() - 1) return dfs(map, up, ""); // 開始構建下一層

int start = up.length();

int end = start + 2;

List values = map.get(boom.substring(start, end));

if(values == null) { // 沒有映射關系 當前兩節點構造失敗

return false;

}

for(int i = 0; i < values.size(); i++) {

if(dfs(map, boom, up + values.get(i))) return true; // 試探每一種父節點的可能性，直到找到可以完整構建一行的

}

return false;

}

public Map> getMap(List allowed) { // 轉換映射

Map> map = new HashMap>(); // 用String比Char方便 所以選擇List

for(String s : allowed) {

String key = s.substring(0, 2); // 截取左右子塊作為鍵

String value = s.substring(2,3);

if(map.containsKey(key)) {

map.get(key).add(value);

} else {

List values = new ArrayList();

values.add(value);

map.put(key, values);

}

}

return map;

}

}