leetcode 20

20. 有效的括号

描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

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

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

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

法一

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        s = s.replace("()", "");
        s = s.replace("{}", "");
        s = s.replace("[]", "");
        return s.length() == 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

该方法不太全面，法二会更好一些

法二

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        if (s.length() % 2 != 0) {
            return false;
        }
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' :
                    st.push(')');
                    break;
                case '{' :
                    st.push('}');
                    break;
                case '[' :
                    st.push(']');
                    break;
                default:
                    if (st.isEmpty() || st.pop() != c) {
                        return false;
                    }
            }
        }
        return st.isEmpty();
    }
}
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

算法实现

用栈 + 奇偶校验：
当字符串的长度是奇数时，说明有一个括号对一定是匹配不上的直接返回false
扫描字符，当遇到左括号时将对应的右括号压入栈中（当遇到右括号的时候，就不用还找括号的对应关系）
当遇到右括号的时候将栈顶的元素pop出来看一下，如果发现括号不一致，直接返回false
解释：因为一个合格的括号表达式当遇到第一个右括号的时候，栈顶的括号一定是匹配的
遍历完成之后，如果栈空返回true，否则返回false