LeetCode：20. 有效的括号

问题链接

#### 20. 有效的括号

问题描述

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

有效字符串需满足：

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

提示：

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

示例

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

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

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

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

解题思路

核心：栈

• 方法1: 替换字符串
  不停的用()、[]、{}对原字符串进行替换，替换成空字符串；直到无法替换，看一下当前字符串是不是空，不如是空，返回true；反之，存在多余的括号，返回false。

• 方法2: 栈
  首先，检验一下字符串的长度是不是2的整数倍，如果不是，肯定有括号无法进行匹配，直接结束；
  然后，新建一个栈，遍历原字符串：如果遇到左括号，就往栈里扔；如果遇到右括号，取出栈顶元素进行匹配校验，校验失败就直接返回false结束；
  最后，校验一下栈是否为空，如果为空，表示全都匹配完了，返回true；反之，返回false。

代码示例（JAVA）

这里仅展示栈的解法，其中，用了一个map来维护括号对。

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put('}', '{');
            put(']', '[');
        }};
        for (char c : s.toCharArray()) {
            if (!map.keySet().contains(c)) {
                stack.push(c);
            } else {
                if (stack.empty() || stack.pop() != map.get(c)) {
                    return false;
                }
            }
        }
        return stack.empty();
    }
}