算法笔记-有效括号序列题解

描述

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

数据范围：

字符串长度 0≤n≤10000

要求：

空间复杂度 O(n)，时间复杂度 O(n)

方法一：

借助辅助栈——左括号入栈

核心思想：

每次遇到'(','{','['这三种字符的时候，将字符入栈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;      //当括号以正确顺序关闭时则最后的栈为空
}

方法二：

使用replace函数

核心思想：

遇到成对的"()","[]","{}"全部利用语言提供的replace函数替换成空字符，最后只需要判断字符长度等于0，则是合法序列，否则为不合法序列。

核心代码：

public boolean isValid(String s) {
         boolean flag = true;

        while (flag) {
            int len = s.length();
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");

            if (len == s.length()) {
                flag = false;
            }
        }

        return s.length() == 0;
    }

方法三：

借助辅助栈——右括号入栈

核心思想：

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

核心代码：

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();
}