有效的括号

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

有效字符串需满足：

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

分析

初步思考

这个题上大学的时候，就做过无数次，和水仙花数等等一样，印象深刻。
初步思路就是hashMap存储（、{、[。起初值为0。当遇到（、{、[时加1。遇到')'，'}'，']' 则判断hashMap对应的值是否大于0。如果不大于0则认为无效。如果大于0,则将hashMap的值进行减1。直到最后hashMap的值都是0,则认为有效。看似是没问题，但是有bug。例如{(}{)}这种明显不符合要求，但是却符合我们的刚才的解题算法。

继续思考

要解决上述的bug，必须要把先后顺序标记出来。可以看出来，我们左半边符号后进的，那么必须右半边符号先出。这很显然和我们栈的特性是一模一样的，后进先出。也就是说，我们遇到（、{、[时，就把将当前值压入栈中。遇到')'，'}'，']' 就从栈顶取出元素，而HashMap中存储的就是后半部分和前半部分的映射关系。如果取出的元素和hashMap的值对比不一致的话就认为无效，如果遍历结束，则认为是个合法的字符串。

这里借用腐烂的橘子的题解的一个图，来描述这个过程。

答案

     public static boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack();
        Map<Character, Character> hashMap = new HashMap<Character, Character>();
        hashMap.put('}', '{');
        hashMap.put(']', '[');
        hashMap.put(')', '(');
        for (int i = 0; i < s.length(); i++) {
            if (hashMap.containsKey(s.charAt(i))) {
                if (stack.isEmpty())
                    return false;
                if (stack.pop() != hashMap.get(s.charAt(i))) {
                    return false;
                }
            }
            stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }

这里如果我们字符串的长度如果不是偶数，那么肯定有一个符号，没法配对，此种情况肯定不是合法的字符串。

复杂度

• 时间复杂度：O(n)。其中n就是我们字符串的长度。
• 空间复杂度：O(n +∣Σ∣)。其中n就是我们栈中元素的个数，为字符串的一半，∣Σ∣就是hashMap的大小，此处只有六个字符串，所以就是6。

总结

简单题型的题确实不是很难，这个题只要看出是栈，那么问题就变得很简单了。如果看不出是栈，顺着初步思路去解决那个bug的话，至少得有一个标记位来标记最新的左半边符号。hashMap是个好东西，我们在很多算法题都用到了这个，在此建议不熟悉hashMap底层原理的朋友去学习学习。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！