题解 | #括号序列#

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

示例
输入："["
返回值：false

方法一: 栈

将每个左括号存入栈中每次遇到右括号时将栈顶的左括号取出于当前的括号做匹配，如果匹配成功则继续，匹配失败则直接返回false。需要注意的是最后如果栈中还有括号则也是false。

代码：

 char st[40000];
    bool isValid(string s) {
        // write code here
        int n = s.length();
        int fase = 1, tot = 0;
        for(int i = 0; i < n; i ++){    //遍历一遍字符串
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') st[++ tot] = s[i];
            else{
                if(tot > 0){ // 判断
                    if(st[tot] == '(' && s[i] == ')'){
                        tot --;
                    }else if(st[tot] == '[' && s[i] == ']'){
                        tot --;
                    }else if(st[tot] == '{' && s[i] == '}'){
                        tot --;
                    }else{
                        fase = 0;
                        break;
                    }
                }else {
                    fase = 0; break;
                }
            }
        }
//         cout << tot << endl;
        if(tot > 0) fase = 0;
        if(fase) return true;
        else return false;
    }

时间复杂度 O(n) 遍历一遍字符串得出结果
空间复杂度 O(n) 最大情况是整个序列都是左括号所以空间复杂度为O(n)

java replace 类

一个合法的序列中每次一定存在一个或多个() {} [],所以每次将其替换成空直到字符串长度为0即可，如果中间出现了替换前和替换后的长度一致说明该序列不合法

代码

public boolean isValid (String s) {
        // write code here
        boolean fase = true;
        while(s.length() > 0){
            int len = s.length();
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");

            if(len == s.length()){
                fase = false;
                break;
            }
        }
        return fase;
    }

时间复杂度：O(n^2) 最高复杂度会为字符串的长度n*替换复杂度n（replace复杂度为O(n)） = O(n^2)
空间复杂度: O(1) 只使用了若干个变量