字符串 - 有效的括号

20. 有效的括号

题目描述

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

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

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

算法思想

这题是比较简单的括号匹配问题，可以使用栈来实现。
遍历字符串，如果当前字符为左括号，则进行压栈操作；否则，则进行出栈操作，同时判断出栈元素是否为当前字符对应的左括号，如果不是，则说明括号不匹配。
如果最后栈为空，说明字符串中的括号全部匹配成功。

考虑几种特殊的情况：

• 如果字符串的长度为奇数，则肯定不满足括号匹配条件，直接返回false
• 如果字符串为空，则直接返回true

代码实现

class Solution {
    private static final Map<Character, Character> map = new HashMap<>(){
        {
            put('(',')');
            put('[', ']');
            put('{', '}');
        
        }
    };

    public boolean isValid(String s) {
        int i = 0;
        int len = s.length();

        // 如果字符串的长度为奇数，则肯定不满足条件
        if (len % 2 == 1) {
            return false;
        }

        List<Character> stack = new LinkedList<>();
        while(i < len) {
            // 如果当前字符为左括号，则压栈，否则出栈
            if (map.containsKey(s.charAt(i))) {
                stack.add(s.charAt(i));
            } else {
                // 如果栈为空，说明当前字符没有与之匹配的左括号，直接返回false
                if (stack.size() == 0) {
                    return false;
                }
                // 如果压栈的左括号对应的右括号为当前字符，则匹配成功，否则匹配失败
                if (map.get(stack.remove(stack.size() - 1)) != s.charAt(i)) {
                    return false;
                }
            }
            i ++;
        }

        return stack.size() == 0;
    }
}