欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

32.最长有效括号

程序员文章站 2022-07-07 08:06:25
C++解法1:滑动窗口暴力解法class Solution {public: bool isValid(string s) { std::stack mystck; for(char ss : s){ if(ss=='(' || ss=='[' || ss=='{'){ mystck.push(ss); }else if(mystck.empty......

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

相关标签: LeetCode刷题