题解 | #括号序列#

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

示例1
输入："["
返回值：false
示例2
输入："[]"
返回值：true

方法一：借助辅助栈——左括号入栈
核心思想：
        每次遇到'(','{','['这三种字符的时候，将字符入栈stk；而每次遇到')','}',']'这三种字符的时候则让对应的匹配字符出栈。具体规则如下：
1）引入辅助栈stk，遍历字符串，每次遇到'(','{','['字符的时候将字符入栈stk
2）当遇到')','}',']'字符的时候，则检查栈是否空，且顶元素是否为匹配元素（如{和}匹配等），如果栈空或者栈顶元素不为匹配元素则括号序列不合法
3）当栈非空，且栈顶元素为匹配元素，则栈顶元素出栈。
4）循环匹配字符串，直到每次字符处理完
5）检查栈stk是否为空，栈为空则序列合法，否则不合法（当括号以正确顺序关闭时则最后的栈为空）

图解：

核心代码：

bool isValid(string s) {
    stack<char> stk;
    for(int i=0;i<s.size();i++){
        switch(s[i]){
            case '(':
            case '[':
            case '{':
                stk.push(s[i]);     //当前字符为'(','{','['时，元素入栈
                break;
            case ')':        
                if(stk.empty() || stk.top() != '(')    //栈空或者括号栈顶字符与当前字符不匹配，则序列为不合法序列
                    return false;
                stk.pop();                   //匹配的栈顶元素出栈
                break;
            case ']':
                if(stk.empty() || stk.top() != '[')
                    return false;
                stk.pop();
                break;
            case '}':
                if(stk.empty() || stk.top() != '{')
                    return false;
                stk.pop();
                break;
        }
    }
    return stk.empty()?true:false;      //当括号以正确顺序关闭时则最后的栈为空
}

复杂度分析：
        代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于引入额外的栈空间，因此空间复杂度为O(N)，最坏的情况是数组中的元素都为左括号。
时间复杂度O(N)
空间复杂度O(N)

方法二：借助辅助栈——右括号入栈
核心思想：
        借助辅助栈，当遇到'(','[','{'这三种字符的时候则让对应的匹配字符入栈(分别对应')',']','}')，当出现的字符不是'(','[','{'这三种字符时，则先判断栈是否为空或者当前字符是否与栈顶元素一样，当栈空或者当前字符与栈顶字符不一样时，则括号序列不合法，直接返回；否则栈顶元素出栈。遍历字符串直到所有元素遍历完成。最后判断栈是否为空，不为空则括号序列不合法；否则为合法序列。

核心代码：

bool isValid(string s) {
    stack<char> stk;
    for(int i=0;i<s.size();i++){
        if(s[i] == '(')           //当为(字符时，将匹配字符入栈，下同
            stk.push(')');
        else if(s[i] == '[')
            stk.push(']');
        else if(s[i] == '{')
            stk.push('}');
        else{                //当字符不是'(','[','{'这三种字符时，则判断当前字符是否与栈顶元素一样(栈非空时)
            if(stk.empty() || s[i] != stk.top())
                return false;
            stk.pop();
        }
    }
    return stk.empty();
}

复杂度分析：
        代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于引入额外的栈空间，因此空间复杂度为O(N)，最坏的情况是数组中的元素都为右括号。
时间复杂度O(n)
空间复杂度O(n)