当前位置：首页 > news >正文

LeetCode：20. 有效的括号——栈和队列

news 来源：原创 2023/9/22 12:15:17

🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻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;
    }
}