你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

leetcode20.有效的括号——学习笔记

2021-11-3 23:34:07

题目:力扣icon-default.png?t=LA23https://leetcode-cn.com/problems/valid-parentheses/

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

思路 :新建一个栈,遇上"{"时则将"}"压入栈中,遇上"["时则将"]"压入栈中,遇上"("时则将")"压入栈中,然后再一一弹出再跟后续的遇上"}"、"]"、")"匹配,若出现栈提前为空或者出现不匹配的情况则返回false。最后若正常匹配成功的话,最后栈会为空,即返ture;若最后栈不为空则表示出现异常,匹配失败,即返回false。

 1.如传入字符串的长度小于2,则不可能比配成功,返回false。然后新建一个栈stack,方便后续操作。

if(s.length()<2) return false;
Stack<Character> stack = new Stack<>();

 2.按照规则(思路中下划线部分)将“}”或“]”或“)”压入栈中,然后一一弹出,跟传入字符中的“}”或“]”或“)”进行比对配对,若不一致或者stack提前空了则返回false值。

for(char c:s.toCharArray()){
    if(c=='('){
        stack.push(')');
    }else if(c=='['){
        stack.push(']');
    }else if(c=='{'){
        stack.push('}');
    }else if(stack.isEmpty()||c!=stack.pop()){
        return false;
    }
}

 3.若匹配成功,栈stack最后应为空,即为true;若stack最后都不为空,则表示匹配出现了异常,即为false。

return stack.isEmpty();