Longest Valid ParentHeses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        std::stack<const char *> stk;
        if (s.empty()){
            return 0;
        }
        int counter = 0;
        const char * p = s.c_str();
        while(*p){

            char c = *p;
            if (c == '('){
                stk.push(p);
                p++;
                continue;
            }

            if (c == ')'){
                if (!stk.empty() && *stk.top() == '('){
                    stk.pop();
                    counter = max(counter,p - (stk.empty() ? s.c_str() -1 : stk.top()));
                }else{
                    stk.push(p);
                }
                p++;
            }
        }
        return counter;
    }
};

如果想返回最长的字符串，只需要再记下串的起始位置就可以。在这里，用Stack来存放指针而不是char元素一举两得，既可以判断合法关系还可以获取到之前的位置

如果不能使用Stack，并且要求Const space的话，就需要2遍的遍历来解决了

class Solution {
public:
int longestValidParentheses(string s)
{
    int counter = 0;
    int ret = 0;
    int curr_max = 0;
    //forward path
    for(size_t i = 0 ; i < s.length() ; i++)
    {
        if(s[i] == '(')
        {
            counter++;
            curr_max++;
        }
        else if(s[i] == ')')
        {
            counter--;
            curr_max++;
        }
        if(counter == 0)
            ret = ret >= curr_max ? ret : curr_max;
        else if(counter < 0)
        {
            curr_max = 0;
            counter = 0;
        }
    }
    //backward path
    counter = 0;
    curr_max = 0;
    for(int i = s.length() -1; i >=0; i--)
    {
        if(s[i] == ')')
        {
            counter++;
            curr_max++;
        }
        else if(s[i] == '(')
        {
            counter--;
            curr_max++;
        }
        if(counter == 0)
            ret = ret >= curr_max ? ret : curr_max;
        else if(counter < 0)
        {
            curr_max = 0;
            counter = 0;
        }
    }
    return ret;
}
};

为什么要进行反向做一遍，是为了解决 (() 这种情况 因为 counter > 0 ，只有认为 ) 多了才认为应该refresh计数器
原文链接: https://www.cnblogs.com/kwill/archive/2013/06/04/3117342.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍