LC 756. Pyramid Transition Matrix
2024-09-05 07:58:30
We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like `'Z'`.
For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A` and right block of color `B`. We are allowed to place the block there only if `(A, B, C)` is an allowed triple.
We start with a bottom row of bottom
, represented as a single string. We also start with a list of allowed triples allowed
. Each allowed triple is represented as a string of length 3.
Return true if we can build the pyramid all the way to the top, otherwise false.
Example 1:
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
A
/ \
D E
/ \ / \
X Y Z This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.
Example 2:
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
Note:
bottom
will be a string with length in range[2, 8]
.allowed
will have length in range[0, 200]
.- Letters in all strings will be chosen from the set
{'A', 'B', 'C', 'D', 'E', 'F', 'G'}
.
map + backtracing
Runtime: 9 ms, faster than 80.22% of Java online submissions for Pyramid Transition Matrix.
class Solution {
private Map<String, List<Character>> mp = new HashMap<>();
public boolean pyramidTransition(String bottom, List<String> allowed) {
for(int i=; i<allowed.size(); i++){
String tmp = allowed.get(i).substring(,);
if(mp.containsKey(tmp)){
mp.get(tmp).add(allowed.get(i).charAt(allowed.get(i).length()-));
}else{
mp.put(tmp, new ArrayList<>());
mp.get(tmp).add(allowed.get(i).charAt(allowed.get(i).length()-));
}
}
// for(String s : mp.keySet()){
// System.out.print(s + " " + mp.get(s) + "\n");
// }
return helper(bottom, "", );
}
public boolean helper(String bottom, String up, int index){
if(bottom.length() == ){
return true;
}else {
String tmp = bottom.substring(index, index+);
if(!mp.containsKey(tmp)) return false;
List<Character> clist = mp.get(tmp);
if(index+ == bottom.length()){
for(char x : clist){
String finalup = up + String.valueOf(x);
if(helper(finalup, "", )) return true;
}
}else {
for(char x : clist){
if(helper(bottom, up+String.valueOf(x), index+)) return true;
}
}
}
return false;
}
}
最新文章
- Mac环境下Octopress个人博客搭建
- 贪吃蛇的java代码分析(二)
- UE4.11新特性:胶囊体阴影
- 【Alpha版本】冲刺-Day6
- gitlab安装部署
- 在线聊天室的实现(1)--websocket协议和javascript版的api
- Android 界面排版的5种方式
- mysql引擎区别
- hdu 3333 Turing Tree 图灵树(线段树 + 二分离散)
- DataGridView添加复选框并向其中绑定值
- tabBar隐藏与显现 hidesBottomBarWhenPushed
- Nginx日志增长过快详细分析
- HDU-1166-敌兵布阵(线段树)
- 转接口IC NCS8807:LVDS转MINI LVDS芯片
- Linux 库文件详解
- 利用Java泛型实现简单的泛型方法
- Android实现横屏以及全屏的小技巧
- java对象之----(PO,VO,DAO,BO,POJO)
- 4.8Python数据处理篇之Matplotlib系列(八)---Figure的学习
- python套接字编程基础