一.题意整理

NC52括号序列

给出一个仅包含字符'(',')','{','}','[',']'的字符串,判断给出的字符串是否是合法的括号序列,括号必须以正确的顺序合并,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。

二.思路整理

判断括号序列是否合法的问题,一般都是用栈这种数据结构去做。

图片说明

本题中,我们可以定义一个栈st,然后遍历字符串:

(1)当遇到左括号:'(', '[',,'{'或者栈为空时,就将当前位置的字符入栈。
(2)如果遇到右括号时,就比对当前字符和栈顶字符是不是对应的括号。
(3)如果不对应或者栈此时失控,那么直接返回false,说明这个字符串不是合法的括号序列
(4)如果是对应的括号,那么就把栈顶的字符出栈,进行下一次循环。 

最终,如果栈是空,就返回true,栈不为空,就返回false。

三.代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<int>st;
        //遍历所以字符串
        for(int i=0;i<s.size();i++){
            //对左边的符号进行匹配
            if(s[i]=='('){
                st.push(')');
            } else if(s[i]=='{'){
                st.push('}');
            } else if(s[i]=='['){
                st.push(']');
            } else {
                //要是右边的符号 进行分情况讨论
                if(st.size()==0) return false;//是空直接返回false
                //要是可以匹配直接将栈顶出栈
                if(st.top()==s[i]){
                    st.pop();
                }
            }
        }
        //是空栈直接返回true
        if(!st.size()) return true;
        return false;
    }
};

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

空间复杂度:O(n)O(n),栈需要空间来存储字符