栈｜ Leetcode 20

Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

2、解题思路：

括号匹配是使用栈解决的经典问题。题意其实就像我们在写代码的过程中，要求括号的顺序是一样的，有左括号，相应的位置必须要有右括号。
有三种括号不匹配的情况：
第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配 return false。
第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符 return false。
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false。

3、代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack = new Stack<>();
        char[] chars = s.toCharArray();
        // 如果s的长度为奇数，一定不符合要求
        if (chars.length % 2 != 0) {
            return false;
        }
        for(char c: chars){
            if(c=='(') {
                stack.push(')');
            } else if(c=='[') {
                stack.push(']');
            } else if(c=='{') {
                stack.push('}');
                // 第二、三种情况
            } else if(stack.isEmpty()||c!=stack.pop()) {
                return false;
            }
        }
        // 第一种情况
        return stack.isEmpty();
    }
}

class Solution {
    public boolean isValid(String s) {
        // 创建一个栈
        Stack<Character> stack = new Stack<>();
        // 遍历输入字符串的每个字符
        for (char c : s.toCharArray()) {
            // 如果是左括号，则将其压入栈中
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // 如果是右括号
            else if (c == ')' || c == ']' || c == '}') {
                // 如果栈为空，则说明右括号没有对应的左括号，返回false
                if (stack.isEmpty()) {
                    return false;
                }
                // 弹出栈顶元素，判断是否匹配
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    // 如果不匹配，返回false
                    return false;
                }
            }
        }
        // 如果栈不为空，则说明左括号多于右括号，返回false
        return stack.isEmpty();
    }
}

参考文章：
https://leetcode.cn/problems/valid-parentheses/comments/