【栈】

【栈】

算法原理

定义一个栈 如果是右括号，就放进栈中 如果是左括号，就判断这个字符 和 栈顶元素（同时出栈）是否匹配 如果不匹配就返回false 那么如果匹配那么就会出栈 最终栈为空 则返回 true 栈 不为空 就返回 false

自己写的（思路清晰）：

 class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0){
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for(char c : ()){
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }
            if(stack.isEmpty()){
                return false;
            }
            
            if(c == ')'){
                if(stack.peek() == '('){
                    stack.pop();
                }else{
                    return false;
                }
            }else if(c == ']'){
                if(stack.peek() == '['){
                    stack.pop();
                }else{
                    return false;
                }
            }else if(c == '}'){
                if(stack.peek() == '{'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

优化后：

 class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0) return false;
        
        Stack<Character> stack = new Stack<>();
        for(char c : ()){
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else {
                if(stack.isEmpty()) return false;
                char top = stack.pop();
                if(c == ')' && top != '(' || 
                    c == ']' && top != '[' || 
                    c == '}' && top != '{' ){
                    return false;
                } 
            }
        }
        return stack.isEmpty();
    }
}

时间复杂度： O() 其中n是字符串的长度 空间复杂度： O() 其中n是字符串的长度