LeetCode20-有效的括号

题目描述

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

有效字符串需满足：

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

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

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

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

示例 4：
输入：s = “([])”
输出：true

示例 5：
输入：s = “([)]”
输出：false

思路

相比大家在学习数据结构中的栈时，都学过怎么利用栈来对逆波兰表达式求解了。遇到左侧括号先入栈，遇到右侧括号则弹出栈顶元素，判断是否匹配。如果匹配消去，如果不匹配直接返回匹配失败，最后再看栈中的元素是否清空，没有的话就表示不完全匹配。

代码实现

Java 代码实现如下：

class Solution20 {
    public boolean isValid(String s) {
        Map<Character, Character> map = Map.of('(', ')', '[', ']', '{', '}');
        char[] charArray = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : charArray) {
            if (map.containsKey(c)) {
                stack.push(c);
            } else if (map.containsValue(c)) {
                if (stack.isEmpty()) {
                    return false;
                }
                Character pop = stack.peek();
                if (c != map.get(pop)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}