🍁每日推荐：
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
『牛客|每日一题』有效括号序列
1.每日一题
2.方法1：左括号入栈
2.1思路分析
遍历字符串，遇到'(','{','['这三种字符的时候，将字符入栈stk；而遇到')','}',']'这三种字符的时候则让对应的匹配字符出栈。具体规则如下：
- step 1：引入辅助栈stk，遍历字符串，每次遇到
'(','{','['字符的时候将字符入栈stk - step 2：当遇到
')','}',']'字符的时候，则检查栈是否空，且顶元素是否为匹配元素（如{和}匹配等），如果栈空或者栈顶元素不为匹配元素则括号序列不合法 - step 3：当栈非空，且栈顶元素为匹配元素，则栈顶元素出栈。
- step 4：循环匹配字符串，直到每次字符处理完
- step 5：检查栈stk是否为空，栈为空则序列合法，否则不合法（当括号以正确顺序关闭时则最后的栈为空）
2.2核心代码
importjava.util.*;
publicclassSolution {
/**
* @param s string字符串
* @return bool布尔型
*/
publicbooleanisValid (Strings) {
// write code here
Stack<Character>stk=newStack<Character>();
intl=s.length();
for(inti=0;i<l;++i){
chara=s.charAt(i);
if(a=='('||a=='['||a=='{')stk.push(a);
if(a==')'){
if(stk.isEmpty()||stk.peek()!='(') returnfalse;
stk.pop();
continue;
}
if(a==']'){
if(stk.isEmpty()||stk.peek()!='[')returnfalse;
stk.pop();
continue;
}
if(a=='}'){
if(stk.isEmpty()||stk.peek()!='{')returnfalse;
stk.pop();
continue;
}
}
returnstk.isEmpty()?true:false;
}
}
3.方法2：右括号入栈
3.1思路分析
仍然是遍历字符串，借助辅助栈
- step 1：当遇到
'(','[','{'这三种字符的时候则让对应的匹配字符入栈(分别对应')',']','}') - step 2：当出现的字符不是
'(','[','{'这三种字符时，则先判断栈是否为空或者当前字符是否与栈顶元素一样， - step 3：当栈空或者当前字符与栈顶字符不一样时，则括号序列不合法，直接返回；
- step 4：否则栈顶元素出栈。遍历字符串直到所有元素遍历完成。最后判断栈是否为空，不为空则括号序列不合法；否则为合法序列。
3.2核心代码
importjava.util.Stack;
publicclassSolution {
publicbooleanisValid(Strings) {
Stack<Character>stack=newStack<Character>();
//使用foreach循环
for (charc : s.toCharArray()) {
if (c=='(')
stack.push(')');
elseif (c=='{')
stack.push('}');
elseif (c=='[')
stack.push(']');
elseif (stack.isEmpty() ||stack.pop() !=c)
returnfalse;
}
returnstack.isEmpty();
}
}
📚订阅专栏：『牛客刷题集锦』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
