题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

解题思路

【算法原理】

• 栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；

• 建立哈希表 pairs 构建左右括号对应关系：key 左括号，value 右括号；这样查询 2 个括号是否对应只需 O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程判断。

【算法流程】

1. 如果 ch 是左括号，则入栈 push；

2. 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 ch 不对应，则提前返回 false。

【代码】

public class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        //奇数
        if (len % 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 < len; 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();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValid("()[]{}"));
    }
}

leetcode20-有效的括号（栈+HashMap）