• 时间：2022-05-22
• 题目序号：20
• 难度：简单

问题描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

来源：力扣（LeetCode）

示例1

输入：s = "()"
输出：true

示例2

输入：s = "()[]{}"
输出：true

示例3

输入：s = "(]"
输出：false

示例4

输入：s = "([)]"
输出：false

示例5

输入：s = "{[]}"
输出：true

提示

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解题思路

题解部分参考自代码随想录。如有侵权，请联系进行删除~~

• 从题目来看，这题使用栈来实现的话，还是比较好理解的
• 遍历字符串，如果遇到左括号，就把它对应的右括号入栈（方便和右括号进行匹配）
• 如果遇到右括号，就将栈顶元素弹出，和该右括号对比，判断是否匹配

到这里，大家先不要急着写代码，先来想想不匹配的情况都有哪几种：

1. 就是当前字符为右括号，与栈顶左括号不匹配，这个比较容易想到
2. 当匹配完后，栈内还有元素（不为空），如下图，也是不匹配的

3. 当字符串未匹配完，但栈内已经没有左括号与之匹配了

• 在写代码时，需要注意将以上三种情况都做出判断

代码实现

除了上述三种不匹配情况，本着一一对应原则，如果能匹配的上，字符串长度一定是偶数，因此可以先对此进行判断，如果为奇数，则一定不匹配

注意：偶数不一定匹配（如题解中的图2），但是奇数一定不匹配

题目中明确说明了只包含{}[]()括号，所以我们不需要考虑其他的括号

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0) return false;
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for(int i = 0; i < s.length(); i++){
            ch = s.charAt(i);
            // 如果是左括号，就把对应的右括号入栈
            if(ch == '(') deque.push(')');
            else if(ch == '{') deque.push('}');
            else if(ch == '[') deque.push(']');
            // 右括号匹配
            else if(deque.isEmpty() || deque.peek() != ch){  // 判断是否是第1、3中不匹配情况
                return false;
            }
            else deque.pop();       // 如果匹配，就弹出栈顶元素
        }
        return deque.isEmpty();     // 判断是否是第二种不匹配情况
    }
}

总结

• 栈的使用场景还是比价广泛的：浏览器的前进后退、递归的实现、类似括号的匹配算法等等

• 本题还是比较经典的，但是也有很多容易弄错的地方

  • 如果是左括号，是将对应的右括号入栈，方便后面的匹配判断
  • 在判断是否是第3种不匹配情况时，是使用peek方法而不是pop
    pop方法会将元素移除，peek只是获取结点，不会将其弹出栈