题解 | #有效括号序列#

一.题意整理

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)$，栈需要空间来存储字符