32. 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.

Difficulty: Hard

这道题比20. Valid Parentheses 验证括号难一些.

解法1

还是利用栈来求解,并定义start记录合法括号串的起始位置.遍历字符串,如果遇到左括号,则将当前下标压栈,如果遇到右括号,如果当前栈为空,则将下一个位置的下标记为start,如果栈不为空,则将栈顶元素取出.此时如果站为空,则更新结果和i-start+1的最大值,否则更新结果为i-栈顶元素的最大值.

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0,start = 0;
        stack<int> m;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='(')
                m.push(i);
            else if (s[i]==')')
            {
                if (m.empty()) start=i+1;
                else
                {
                    m.pop();
                    res = m.empty()?max(res,i-start+1):max(res,i-m.top());
                }
            }
        }
        return res;
    }
};

解法2

利用DP来求解.构建一个longest[]来存储在i出的最常合法括号串.

DP的思路如下:

if s[i]=='(',longest[i]=0,因为'('不可能为合法括号串
else if s[i]==')'
	if  s[i-1]=='(', longest[i] = longest[i-2]+2
	else if s[i-1]==')' && a[i-longest[i-1]-1]=='(', longest[i] = longest[i-1]+2+longest[i-longest[i-1]-2] 
	//比如输入"()(())",longest array [0,2,0,0,2,0],longest[5] = longest[4] + 2 + longest[1] = 6;
class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.length()<=1) return 0;
        int curMax = 0;
        vector<int> longest(s.size(),0);
        for (int i=1;i<s.length();i++)
        {
            if (s[i]==')')
            {
                if (s[i-1]=='(')
                {
                    longest[i] = (i-2)>=0?longest[i-2]+2:2;
                    curMax = max(longest[i],curMax);
                }
                else //s[i-1]==')'
                {
                    if (i-longest[i-1]-1>=0&&s[i-longest[i-1]-1]=='(')
                    {
                        longest[i] = longest[i-1]+2+((i-longest[i-1]-2>=0)?longest[i-longest[i-1]-2]:0);
                        curMax = max(curMax,longest[i]);
                    }
                }
            }
        }
        return curMax;
    }
};
 
comments powered by Disqus