LeetCode 20.有效的括号

1 题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

来源：力扣（LeetCode）
链接：20.有效的括号

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

2 算法设计

本题目主要考察栈的应用，由于栈的结构特点（先进后出），因此栈最适合用来括号匹配。
根据题目可知，括号匹配过程中有三种不匹配的情况：
（1）第一种情况，字符串里的左括号多余了，所以不匹配。

（ [ { } ] （）
1

分析：该种情况已经遍历完了字符串，但是栈不为空，说明有相应的左括号，但是没有找到对应的右括号，所以返回fasle
（2）第二种情况，字符串里的右括号多余，所以不匹配。

（ [ { } ] ）[
1

分析： 这种情况下，在遍历字符串匹配的过程中，栈已经为空了，说明右括号没有找到对应的左括号，返回false
(3)第三种情况，字符串里的括号不多余，但是出现不匹配的情况。

（ { { } ] ）
1

分析： 遍历字符串匹配的过程中，发现栈里没有要匹配的字符，返回false
结合上面出现的三种可能的匹配情况，如果字符串遍历完之后，栈是空的，就说明左括号和右括号全都匹配了。
算法思想： 首先遍历字符串里所有的字符，如果遇到左括号如‘（’、‘[’、'{'则将对应的右括号入栈，这样主需要比较当前比较元素和栈顶元素是否相等即可。

3 代码实现

public  boolean isValid(String s) {
		//初始化栈，用于存储右括号
        Deque<Character> deque = new LinkedList<>();
        for (char c : s.toCharArray()){
            if (c == '('){
                deque.push(')');
            }else if (c == '{'){
                deque.push('}');
            }else if (c == '['){
                deque.push(']');
            }else if (deque.isEmpty() || c != deque.peek()){
            //字符遍历过程中栈为空或者当前元素不匹配  
                return false;
            }else { //当前字符与栈中元素相等，说明匹配，出栈
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4 结果