描述

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

示例1

输入：
"["

返回值：
false

示例2

输入：
"[]"

返回值：
true

思路

这道题主要是判断字符串中括号是否匹配，这道题咱们可以使用一个数据结构来解决，这个数据结构是“栈”。
咱们可以这样做：
1. 开始遍历括号序列，如果是左侧括号，则入栈。
2. 如果碰到右侧括号，则弹出栈定的括号，如果能匹配，则继续重复上面的动作；如果不匹配，则直接判定为不合法的括号序列。
3. 当遍历完时，check一下栈是否为空，如果不为空，说明左侧的括号要多，则判定为不合法的括号序列；否则就是合法的括号序列。

如下图所示：  

AC 代码

    public boolean isValid (String s) {
        // write code here
        if (s == null || s.length() < 1) {
            return false;
        }
        // 如果长度时奇数，则直接判定为不合法的括号序列
        if ((s.length() & 1) == 1) {
            return false;
        } 

        Map<Character, Character> map = new HashMap<>();
        map.put(']', '[');
        map.put('}', '{');
        map.put(')', '(');
        // 用栈来存储每次遍历的括号
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            // 如果是右侧括号（']', '}', ')'）,那么就需要去栈里弹出最顶端的字符，
            // 看下是否能和这个右侧括号匹配，如果栈为空或不匹配，则说明括号序列不合法
            if (map.containsKey(c)) {
                // 如果栈为空，则不合法
                if (stack.isEmpty()) {
                    return false;
                }
                char ch = stack.pop();
                // 如果栈弹出的括号不匹配，则不合法
                if (ch != map.get(c)) {
                    return false;
                }
            } else {
                // 如果不是右侧括号，则入栈
                stack.push(c);
            }
        }
        // 最后需要看一下栈是否为空，如果还有为匹配的，则不合法
        return stack.isEmpty() ? true : false;
    }

时间复杂度；O(n),n 为字符串的长度
空间复杂度：O(n)，最多就是把所有的字符放到栈中

最后

这道题主要是要选对数据结构“栈”，其余的都不是啥问题。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。