LeetCode——有效括号

NO.20 有效括号简单

思路一：栈 学校的数据结构课就是那这个作为例子来引入栈结构的。1. 遍历表达式中每个字符，如果是’(‘或’[]’或’{‘就放入栈中。2. 如果是’)’或’]’或’}’就弹出栈顶字符top，如果此时栈为空或者将此时被遍历字符和top不匹配，则说明表达式无效。3. 遍历完所有字符，检查栈是否为空，如果不为空则表达式无效，反之有效。

public boolean isValid(String s) {
        if (s==null||s.equals(""))return true;
//        用hashmap存储括号对
        HashMap<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);
//            如果map中没有c这个key，则说明c是(或[或{,就存入栈中（题目说只有六种字符）
            if (!map.containsKey(c)){
                stack.push(c);
            }else {//如果存在c这个key则说明，c是)或]或}，就需要去和栈顶字符进行匹配
//                如果栈为空，则无法匹配
                if (stack.size()==0)return false;
//                取出栈顶元素
                Character top = stack.pop();
//                如果map中c的value和栈顶元素top不相等，则无法匹配
                if (map.get(c)!=top)return false;
            }
        }
//        遍历完所有字符之后，检查栈是否为空，如果为空则匹配，反之无法匹配
        return stack.isEmpty();
    }

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.20 有效括号 简单

NO.20 有效括号简单