20. 有效的括号(简单，但值得多看)

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

示例 2:

输入: “()[]{}”
输出: true

示例 3:

输入: “(]”
输出: false

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

思路：

这里判断括号合不合法，这里需要进行以下几步，这里用栈来做，没其他好办法

  1. 遇到左括号，入栈
  2. 栈空时遇到右括号，错
  3. 遇到右括号，匹配栈顶元素，如果可以匹配为同一个，则正确
  4. 当栈全空时，未报错则正确

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean isValid(String s) {
        //定义一个map,使用char报错，因为HashMap的key和value可以为null，但java基本类型不允许为null
        //HashTable均不可以为空，区别是什么需要再看
        HashMap<Character,Character> map = new HashMap<Character,Character>();
        map.put(')','(');//右括号放前面,作为key
        map.put(']','[');
        map.put('}','{');
        //借助栈来实现
        Stack<Character> stack = new Stack<Character>();
        //遇到左括号都进入，遇到右括号都弹出栈顶元素
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            //不是左就是右，没有包含，就是左括号，进栈
            if(!map.containsKey(c))
                stack.push(c);
            else{
                // char Top1;
                // //如果栈为空，设栈顶元素为空
                // if(stack.empty()){
                //     Top1='\0';
                // }else{
                //     Top1= stack.pop();
                //     //最顶上的括号
                //     if(Top1!=map.get(c))
                //         return false;
                // }   
                char Top1 = stack.empty()?'\0':stack.pop();
                if(Top1!=map.get(c))
                    return false;
            }
        }        
        return stack.isEmpty();//判断为不为空，这一步很优秀啊,空的话合法，不空非法，也是栈判断的最后一步
    }
}