32.最长有效括号

C++解法1：滑动窗口暴力解法

 

class Solution {
public:
     bool isValid(string s) {
        std::stack<char> mystck;
        for(char ss : s){
            if(ss=='(' || ss=='[' || ss=='{'){
                mystck.push(ss);
            }else if(mystck.empty()){
                return false;
            }else{
                if(ss==')' && mystck.top()=='('){
                    mystck.pop();
                }else if(ss=='}' && mystck.top()=='{'){
                    mystck.pop();
                }else if(ss==']' && mystck.top()=='['){
                    mystck.pop();
                }else{
                    return false;
                }
            }
        }
        if(mystck.empty()){
            return true;
        }else{
            return false;
        }
    }

    int longestValidParentheses(string s) {
       for(int i = s.length(); i>0; --i){
        for(int j = 0; j<=s.length() - i; j++){
            if(isValid(s.substr(j, i))){
                return i;
                }
            }
        }
        return 0;

    }
};

解法2：从左往右遍历一遍，从右往左遍历一遍

class Solution {
public:
    int longestValidParentheses(string s) {
        int depth = 0, start = -1;
        int res = 0;
        //从左往右来一遍
        for(int i = 0; i < s.length(); ++i){
            if (s[i] == '('){
                depth++;//遇到左括号,depth+1, 否则遇到右括号，depth-1
            } else{
                depth--;
                if (depth == 0){ //如果此时depth刚好为0， 更新一波res;
                    res = max(res, i-start);
                }else if(depth < 0){//如果此时depth刚好小于0,则更新起点
                    depth = 0;
                    start = i;
                }
            }
        }
        //从右往左来一遍
        depth = 0;
        start = s.length();
        for(int i = s.length() - 1; i >=0; --i){
            if (s[i] == ')'){
                depth++;
            } else{
                depth--;
                if (depth==0){
                    res = max(res, start - i);
                } else if(depth < 0){
                    depth = 0;
                    start = i;
                }
            }
        }
        return res;
    }
};

 

 

本文地址：https://blog.csdn.net/Haku_yyf/article/details/108585616