当前位置:网站首页>Leetcode bracket validity problem
Leetcode bracket validity problem
2022-07-28 15:39:00 【pshdhx_ albert】
Title Description :
Given one only includes '(',')','{','}','[',']' String s , Determines whether the string is valid .
Valid string needs to meet :
Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .
Input :s = "()" Output :true
Input :s = "()[]{}"
Output :trueInput :s = "(]" Output :false
Input :s = "([)]" Output :false
Input :s = "{[]}"
Output :trueDescription of ideas
There is a closing bracket of the same type to close it . Because the left bracket encountered after must be closed first , So we can put this 【 Put the left bracket at the top of the stack 】.
When we encounter a closing bracket , We need to close an open parenthesis of the same type . here , We can take out the left parentheses at the top of the stack and judge whether they are the same type of parentheses .
If not of the same type , Or there is no left parenthesis in stack , So the string ss Invalid
Be careful :(( and )) In special circumstances .
Code
package com.pshdhx.Algorithm.easy;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author pshdhx
* @date 2022-01-12 15:26
* @Des Valid parenthesis
*/
/**
* Description of ideas : There is a closing bracket of the same type to close it . Because the left bracket encountered after must be closed first , So we can put this 【 Put the left bracket at the top of the stack 】.
* When we encounter a closing bracket , We need to close an open parenthesis of the same type . here , We can take out the left parentheses at the top of the stack and judge whether they are the same type of parentheses .
* If not of the same type , Or there is no left parenthesis in stack , So the string ss Invalid
* Be careful :(( and )) In special circumstances .
*/
public class Brackets {
Boolean isValid(String s) {
// The odd number returns directly to
if(s.length() % 2 == 1){
return false;
}
// Left bracket in stack
// Bracketed queue "{[]}"
Stack<Character> stack = new Stack<>();
if(s.charAt(0) == ')' || s.charAt(0) == ']' ||s.charAt(0) == '}'){
return false;
}
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('
||s.charAt(i)=='['
||s.charAt(i)=='{'){
stack.push(s.charAt(i));
}else if(stack.size()==0){ // solve ()))
return false;
}else if(s.charAt(i)==')' && stack.size()>0){
Character left = stack.pop();
if(left != '('){
return false;
}
}else if(s.charAt(i)== ']' && stack.size()>0){
Character left = stack.pop();
if(left != '['){
return false;
}
}else if(s.charAt(i)== '}' && stack.size()>0){
Character left = stack.pop();
if(left != '{'){
return false;
}
}
}
// solve (( such
if(stack.size()>0){
return false;
}
return true;
}
public static void main(String[] args) {
Brackets b = new Brackets();
Boolean valid = b.isValid("()))");
System.out.println(valid);
}
}
边栏推荐
猜你喜欢

Idea debugging burpsuit plug-in

腾讯面试之--请你设计一个实现线程池顺序执行

详解.NET的求复杂类型集合的差集、交集、并集

Baidu proposes a dynamic self distillation method to realize dense paragraph retrieval by combining interactive model and double tower model

Pycharm - output exception of program run and default comment of added function

百度提出动态自蒸馏方法,结合交互模型与双塔模型实现稠密段落检索

一篇文章了解RSocket协议

爬虫入门(1)——requests(1)

使用Mock技术帮助提升测试效率的小tips,你知道几个?

Svg verification code recognition experience
随机推荐
800V高压系统
Easy start, swagger
2022-07-28日报:Science:AI设计蛋白质再获突破,可设计特定功能性蛋白质
Opencv - draw mask images of multiple instances
关于word文档中插入的图片只显示下面一部分
关于Simulink如何生成模型覆盖率报告
正则表达式(4)
软件架构与设计(七)-----互动架构
生命的感悟
vs动态库调试
Canoe tutorial
Common methods of qcustomplot drawing tools
samba服务器搭建指南
2、开源GPS项目HD-GR GNSS的自叙
有道云笔记去除底部广告
根据输入target,返回数组的两个下标。
Write a standard character device driver with your hands
多线程
Nftscan and nftplay have reached strategic cooperation in the field of NFT data
有奖活动分享:使用WordPress搭建一个专属自己的博客后最高可领取iPhone13