【LeetCode】20、有效的括号

20、有效的括号

题目：

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

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

提示：

1 <= s.length <= 10^4
s 仅由括号 ‘()[]{}’ 组成

解题思路：

1. 首先如果字符串能组成有效的括号，则长度一定是偶数
2. 我们可以遍历字符串，遇到左括号则暂存，期待后面有右括号可以和它匹配
3. 如果遇到右括号则检查是否能和最晚暂存的做括号匹配。
4. 这就和栈这种数据结构先进后出的特性相吻合了。所以我们可以准备一个栈存放括号对
5. 遍历字符串的时候，如果遇到左括号入栈，遇到右括号则判断右括号是否能和栈顶元素匹配，在循环结束的时候还要判断栈是否为空，如果不为空，则不是有效括号匹配的字符串

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

具体代码：

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

        Map<Character, Character> pairs = new HashMap<Character, Character>() {
    {
    
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
    
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
    
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
    
                    return false;
                }
                stack.pop();
            } else {
    
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}