Cinte's Leetcode Record
0%

32. Longest Valid Parentheses

Posted on Edited on In Disqus:
Symbols count in article: 5.5k Reading time ≈ 5 mins.

32. Longest Valid Parentheses

stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int maxLength = 0;
        st.push(-1);
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '(')
                st.push(i);
            else
            {
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    maxLength = max(maxLength, i - st.top());
            }
        }
        return maxLength;
    }
};

stack中存储坐标，括号两端(左端为括号开始的前一个, 右端为当前括号)构成最长的值。先push(-1)是便于计算，每遇到一个)就pop出一个，空的时候就push，为了方便后面计算坐标。

review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestValidParentheses(string s) {
        s.append("(");
        stack<int> st;
        st.push(-1);
        int ret = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            ret = max(i - st.top() -1, ret);
            if(st.size() != 1 && s[i] == ')' && s[st.top()] == '(')
            {
                st.pop();
            }else
                st.push(i);
        }
        return ret;
    }
};
dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size());
        dp[0] = 0;
        int maxLen = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')' && s[i - 1] == '(')
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            else if(s[i] == ')' && s[i - 1] == ')')
            {
                if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

对于s[i] == ')'这时一个括号要收尾

  1. 如果s[i - 1] == '('，则dp[i] = dp[i - 2] + 2
  2. 如果s[i - 1] == ')'，此时如果s[i-1]有配对的'('或者多个合法的配对，那么通过先前这个的长度往前减坐标寻找是否有与s[i]配对的'('若有，则这个与其配对的将之中包裹的合法括号和先前的合法括号连接相加dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size(), 0);
        int ret = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')')
            {
                if(s[i - 1] == '(')
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                else if(s[i - 1] == ')' && (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '('))
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            ret = max(ret, dp[i]);       
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size() + 2);
        int ret = 0;
        dp[0] = dp[1] = dp[2] = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')')
            {
                if(i - dp[i + 1] >= 1 && s[i - dp[i + 1] - 1] == '(')
                {
                    dp[i + 2] = dp[i + 1] + 2 + dp[i - dp[i + 1]];
                    ret = max(dp[i + 2], ret);
                }
            }else
                dp[i + 2] = 0;
        }
        return ret;
    }
};

r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        int n = s.size();
        vector<int> dp(n);
        int ret{0};
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == ')' && i - dp[i - 1] - 1 >= 0)
                dp[i] = s[i - dp[i - 1] - 1] == '(' ? (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2 : 0;
            ret = max(dp[i], ret);
        }
        return ret;
    }
};
two point
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0;
        int maxLength = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '(')
                ++left;
            else if(s[i] == ')')
                ++right;
            if(left == right)
                maxLength = max(maxLength, 2 * right);
            else if(right > left)
                left = right = 0;
        }
        left = right = 0;
        for(int i = s.size() - 1; i >=0; --i)
        {
            if(s[i] == '(')
                ++left;
            else if(s[i] == ')')
                ++right;
            if(left == right)
                maxLength = max(maxLength, 2 * right);
            else if(right < left)
                left = right = 0;
        }
        return maxLength;
    }
};

遇见(就增加left，遇见)就增加right，当二者相等时候，表明所有(和)配对了，计算长度，更新max

从左到右时，当right>left，表示前面遇到的(比)少，因此由于括号的顺序，不可能再长下去了，由此重置left和right继续开始计数

从右往左时，当left>right, 表示前面遇到的)比(少，同理

要从左往右和从右往左都走一遍是因为... 证明：[@wander](https://leetcode.com/wanders/) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Proof of validity for approach 4:

Let i and j denote the starting and ending indices of the longest valid subsequence.
Note that in the forward pass after (fully) processing each character, it's always the case that left >= right. (*)
This is in particular true after processing i-1 (immediately before processing i).

Case 1: If immediately before i left = right, then the forward pass will detect the length of the longest valid subsequence.
(The number of '(' and ')' is the same for any valid subseq. Thus after processing j, left = right.)

Case 2: If immediately before i left > right, the forward pass will not detect the longest valid subsequence, but we claim the backward pass will.
Similar to observation (*) above, note that right >= left after fully processing each element in the backward pass. We detect the longest valid subsequence in the backward pass if and only if right = left after processing j+1 (immediately before processing j).
So what if right > left (in the backward pass immediately before processing j)?
Well, then the maximality of our subsequence from i to j would be contradicted.
Namely, we can increase j to j' so that (j,j'] has one more ')' than '(', and decrease i to i', so that [i',i) has one more '(' than ')'.
The resulting subsequence from i' to j' will have longer length and will still be valid (the number of '(' and ')' will be incremented by the same amount).

Thus, either the backward pass or forward pass (possibly both) will detect the longest valid subsequence.

Edit: as @papercup points out in response to @bmunot9 , one can take i' = i - 1 and j' = j + 1, since

left > right immediately before i in the forward pass implies that s[i] == '(', otherwise maximality would already be contradicted (one could find i0<i such that s[i0,i) is valid, and thus s[i0,j] would be valid). Similarly
right > left immediately after j+1 (before j) in the backward pass implies s[j] == ')'
左边走不到的右边必然走的到，否则矛盾，具体见上面