Wednesday, November 26, 2014

[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;
    }
};

1 comment:

  1. 思路1 dp 的通项 s[i] = '(':DP[i] = 0 ,是不是应该改为 s[i-1] = '(':DP[i] = 0 ?

    ReplyDelete