🌻算法,不如说它是一种思考方式🍀
算法专栏: 👉🏻123
一、🌱20. 有效的括号
-
题目描述:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。 -
来源:力扣(LeetCode)
-
难度:简单
-
提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成 -
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
🌴解题
题目要求判断字符串是不是合法括号组合,也就是找到一个左括号,还要在后面有一个可以连接的有括号。这时候我们使用栈这种先进后出数据结构就很方便,当左括号进栈,只有匹配到下一个要进栈的是右括号,也就是找到一个匹配括号,将其弹出栈。而如果进栈一个不能弹出栈的右括号,这时候肯定括号存在交叉或者不匹配,可以提前退出返回false
。只有当最后栈为空才返回true
,否则返回false
。
使用栈
为了熟悉栈,我们可以实现一个栈及其方法:
class MyStack {
List<String> mystack=new ArrayList<>();
public MyStack() {
}
public void push(String x) {//进栈
mystack.add(x);
}
public String pop() {//弹出栈顶
String x=mystack.get(mystack.size()-1);
mystack.remove(mystack.size()-1);
return x;
}
public String peek() {//栈顶
return mystack.get(mystack.size()-1);
}
public boolean empty() {
return mystack.isEmpty();
}
}
- code:
class Solution {
public boolean isValid(String s) {
MyStack stack=new MyStack();
for (int i = 0; i < s.length(); i++) {
if(!stack.empty()){//栈非空,就可以判断括号匹配
switch(stack.peek()){
case "(":
if(s.charAt(i)==')')stack.pop();
else
stack.push(String.valueOf(s.charAt(i)));break;
case "[":
if(s.charAt(i)==']')stack.pop();
else
stack.push(String.valueOf(s.charAt(i)));break;
case "{":
if(s.charAt(i)=='}')stack.pop();
else
stack.push(String.valueOf(s.charAt(i)));break;
default:return false;
}
}else
stack.push(String.valueOf(s.charAt(i)));
}
if(!stack.empty())
return false;
return true;
}
}
返回第一页。☝
☕物有本末,事有终始,知所先后。🍭
文章来源:https://www.toymoban.com/news/detail-426142.html
🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓 文章来源地址https://www.toymoban.com/news/detail-426142.html
到了这里,关于LeetCode:20. 有效的括号——栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!