20. 有效的括号

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

解题

public boolean isValid(String s) {
        //先用map把括号对存起来，key：左括号；value：右括号；
        // 这样配对起来时间复杂度就为O(1);
        //防止栈为空时报错，加入('?','?')
        Map<Character,Character> map = new HashMap<Character,Character>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        map.put('?','?');
        //排除几种特殊情况：
        if(s.equals("")){
            return true;
        }
        if(s.length()%2==1){
            return false;
        }
        if(s.charAt(0)==')'||s.charAt(0)==']'||s.charAt(0)=='}'){
            return false;
        }
        //初始化栈，然后循环s,如果是左括号，先入栈，并且把它放在stack的last；
        //如果有跟它配对的右括号出现，就将它移除，如果最后正好都配对完，剩下的就是最开始的那个'？'
        LinkedList<Character> stack = new LinkedList<Character>();
            stack.add('?');
        for(Character c:s.toCharArray()){
            //map如果包含key，证明就还是左括号
            if(map.containsKey(c)){
                stack.addLast(c);
//                map不包括key了，那证明应该是出现了一个右括号，如果符合一对括号，
//                那它和栈里面的最后一个括号之间，肯定不能有其他形式的括号
//                所以把栈里的最后一个从map里get出来，看是否跟右括号一样
            }else if(map.get(stack.removeLast())!=c){
                return false;
            }
        }
        return stack.size()==1;
}

j结果

执行用时 :5 ms, 在所有 Java 提交中击败了79.77%的用户
内存消耗 :35.1 MB, 在所有 Java 提交中击败了82.28%的用户