[NC]52. 有效括号序列

🚩传送门：牛客题目

题目

给出一个仅包含字符'(',')','{','}','['']的字符串，判断给出的字符串是否是合法的括号序列

示例1

输入：“[“ 返回值：false

解题思路：栈

遍历字符串，遇 ( 或 [ 或 { 入栈，否则吐出栈顶元素与当前的字符进行匹配，不匹配返回false
当遍历字符串结束后，栈空说明匹配，否则说明不匹配。

复杂度分析

时间复杂度：，其中 为字符串的长度 。

空间复杂度：，其中 为字符串的长度，最差情况所有字符全部入栈 。

官方代码

public class Solution {
    public boolean isValid (String s) {
        Stack stack=new Stack();
        // 遍历字符串
        for(int i=0;i<s.length();i++){
            // 遇见 ( 或 [ 或 { 入栈
            if(s.charAt(i)=='['||s.charAt(i)=='('||s.charAt(i)=='{')
                stack.push(s.charAt(i));
            else{    
                // 说明此时是 ) 或 } 或 ] 
                // 栈空说明不匹配
                if(stack.empty())return false;
                char c=(char)stack.pop();
                if(s.charAt(i)==']'){
                    if(c!='[')return false;
                }
                else if(s.charAt(i)==')'){
                    if(c!='(')return false;
                }else if(s.charAt(i)=='}'){
                    if(c!='{')return false;
                }else
                    return false;
            }
        }
        // 字符串遍历完成后，栈空说明匹配成功,否则失败
        if(stack.empty())return true;
        return false;
    }
}