题解 | #括号序列#

一.题目描述
NC52括号序列
题目链接:
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=196&&tqId=37083&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一个仅包含字符'(',')'，'{','}'，'['和']'的字符串，判断给出的字符串是否是合法的括号序列，括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
二.算法(栈)
判断括号序列是否合法的问题，一般都是用栈这种数据结构去做。

本题中，我们可以定义一个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),其中n是字符串的长度
空间复杂度：o(n)，栈需要空间来存储字符
优缺点：个人感觉只有优点，时间复杂度低，而且便于实现。
三.算法(java实现模拟栈)
思路和算法二一样，但是java手动用StringBuffer模拟一个栈，遍历字符串，时间上和算法二一样，但是在空间上占优，下面直接看代码：

import java.util.*;
class Solution {
    public boolean isValid(String s) {
        StringBuffer ant = new StringBuffer();
        int n = s.length();
        char c, cc;
        for(int i = 0; i < n; i++){
            c = s.charAt(i);
            if(c == '(' || c == '{' || c == '['){
                //要是全都是左边的符号 就直接添加到栈里面
                ant.append(c);
            }else{
                if(ant.length() == 0) return false;//要是空直接返回false
                cc = ant.charAt(ant.length() - 1);//cc表示栈顶元素
                if((cc == '(' && c == ')') || (cc == '{' && c == '}') || (cc =='[' && c == ']')){
                    //匹配成功直接删除末尾元素，穆模拟于出栈
                    ant.deleteCharAt(ant.length() - 1);
                    continue;
                } else{
                    return false;
                }
            }
        }
        //同样判断模拟栈最后是不是空
        if(ant.length() == 0)
            return true;
        else
            return false;
    }
}

时间复杂度：o(n)
空间复杂度：o(n)
优缺点：实现起来相比算法二复杂，但是空间利用率高