关阿姨带你横扫LeetCode系列之有效的括号

关阿姨正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

首先跟大家阐明一点就是，每道算法题都有多种解法，我们只讲LeetCode上几种优秀的解题思路~，希望

可以帮助到大家，那我们先来看下题目描述吧~

一、题目描述：

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例：
输入: “()” 输出: true
输入: “()[]{}” 输出: true
输入: “(]” 输出: false
输入: “([)]” 输出: false
输入: “{[]}” 输出: true

二、思路分析：

我们知道有效的括号，一定是一个左括号对应一个右括号；而嵌套的括号，先出现的左括号，要后出现其相应的右括号。也就是说，我们在遍历这个字符串时，最先出现的左括号，要最后判断其是否有对应的右括号。这个顺序大家是不是就想到栈？栈就是先进后出的啊，我们可以把遍历的括号存放在栈里，然后遇到对应的右括号时，拿出栈顶的左括号与其进行判断是否是同一个类型，直到遍历完成后，看栈里是否还存在元素，若存在则说明，括号没有全部对应上，就是无效的；若不存在则说明，括号已经全部对应上，就是有效的。而且，括号都是成对的，所以当字符串长度是奇数的时候，那一定是无效的啊。有了这个思想，我们来写代码看看：

三、代码演示：

public boolean isValid(String s) {
      int len = s.length();
        //先根据字符串长度是否为奇数，判断是否有效
        if(len % 2 == 1){
            return false;
        }
        //使用map将字符保存
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        //初始化栈，用来保存先遍历出来的左括号
        //为什么是保存左括号呢？因为一对括号一定是左括号在前的，而且我们无法确定到底有几层括号嵌套，因此，先把左括号保存起来，然后通过遍历到的右括号去获取对应的左括号进行判断。这也是为什么map里用右括号做key的原因
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                if(deque.isEmpty() || deque.peek() != map.get(ch)){
                    return false;
                }
                deque.pop();
            }else{
                deque.push(ch);
            }
        }
        return deque.isEmpty();
}
复制代码