[LeetCode] 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.

思路1：DP

求极值问题一般想到DP或Greedy，显然Greedy在这里不太适用，只有用DP了。

1. 状态：
DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。

2. 通项公式：
s[i] = '('：
DP[i] = 0

s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符j = i-2-DP[i-1]
DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
DP[i] = 0，如果j<0，或s[j] = ')'

......... (     x    x    x    x   )
          j                      i-2 i-1

证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
(    x    x    x    x    x
j'  j'+1                  i-1
这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。

3. 计算方向
显然自左向右，且DP[0] = 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int longestValidParentheses(string s) { int n = s.size(), maxLen = 0; vector<int> dp(n+1,0); for(int i=1; i<=n; i++) { int j = i-2-dp[i-1]; if(s[i-1]=='(' || j<0 || s[j]==')') dp[i] = 0; else { dp[i] = dp[i-1]+2+dp[j]; maxLen = max(maxLen, dp[i]); } } return maxLen; } };

思路2：stack

括号题自然又想到了stack。仔细想下，这题目其实是Valid Parentheses的升级版。一个valid parentheses substring必然以'('开头以')'结尾，并且中间一定也是一个valid parentheses substring。这也意味着依照Valid Parentheses解法那样，用stack来存储没有配对的'('和')'，并用相应的')'来消去stack top的'('，最长substring的首尾必然会在这个过程中相消。

1. 由于我们需要知道它们之间的长度，所以stack里可以存储各个'('的坐标。
2. 为了能正确计算类似“ ) ( ) ( ) ”这种valid substring连接而组成的valid substring。我们必须也插入')'进stack，作为边界来计算长度。
3. 为了能在stack中区分左右括号，每个插入item定义为pair<int,int>。first为坐标，second表示左还是右括号。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int longestValidParentheses(string s) { stack<pair<int,int>> stk; // first: index, second: 0:'(', 1:')' int maxLen = 0, curLen = 0; for(int i=0; i<s.size(); i++) { if(s[i]=='(') // left parenthesis stk.push(make_pair(i,0)); else { // right parenthesis if(stk.empty() || stk.top().second==1) stk.push(make_pair(i,1)); else { stk.pop(); if(stk.empty()) curLen = i+1; else curLen = i-stk.top().first; maxLen = max(maxLen, curLen); } } } return maxLen; } };