Java实现 LeetCode 756 金字塔转换矩阵（DFS）Java南 墙-

756. 金字塔转换矩阵

现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。

使用三元组表示金字塔的堆砌规则如下：

对于三元组(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。   

注意：

bottom 的长度范围在 [2, 8]。
allowed 的长度范围在[0, 200]。
方块的标记字母范围为{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}。

class Solution { public boolean pyramidTransition(String bottom, List<String> allowed) { if(allowed==null||allowed.size()==0)return false;         HashMap<String,List<String>> dir=new HashMap<>(16); for(String str:allowed) {             String head=str.substring(0,2);             String ch=str.substring(2,3); if(dir.containsKey(head)) {                 dir.get(head).add(ch); } else {                 List<String>p=new ArrayList<>();                 p.add(ch);                 dir.put(head,p); } } return(dfs(bottom, "",dir)); } static boolean dfs(String last,String now,HashMap<String,List<String>> dir){ if(last.length()==2&&now.length()==1) { return true; } if(now.length()==last.length()-1){ return dfs(now,"",dir); } int start=now.length();int end=now.length()+2;         List<String> p=dir.get(last.substring(start, end)); if(p==null) return false; for (int i = 0; i < (p).size(); i++) { if(dfs(last,now+p.get(i),dir)) { return true; } } return false; } }