Description

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

Example

1
2
3
4
5
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.

Interface

1
2
3
4
5
6
class Solution {
public:
    int longestValidParentheses(string s) {

    }
};

Solution

一开始只是简单的以为是求出所有合法的圆括号的数量，就直接用一个栈去写，提交后才发现理解错了，原来题目的意思是从找出字符串中最长的合法圆括号子串的长度。

重新审题后就能发现每个合法的字串其实都是由不合法的字串分隔开的，我的思路是用一个栈存储 pair<char, int> 类型的元素，char 为圆括号字符，int 为此时所有合法的圆括号数量。当栈顶元素字符为 ‘(‘ 且当前字符为 ‘)’ 时，就将栈顶元素 pop 出，并将合法圆括号数量 +2，到最后栈中留下的都是不合法的圆括号，其实就相当于将合法的圆括号字串分隔开的分隔符，此时就可以利用这些分隔符求出每个合法圆括号字串的长度，取最大的字串长度即可。算法的复杂度是 $O(n^2)$。

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
32
33
34
35
36
37
38
39
class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.length() == 0) return 0;
        int count = 0, max = 0;
        stack<pair<char, int> > stk;
        pair<char, int> p(s[0], 0);
        stk.push(p);
        for (int i = 1; i < s.length(); ++i) {
            if (stk.empty()) {
                pair<char, int> temp(s[i], count);
                stk.push(temp);
                continue;
            }
            pair<char, int> top = stk.top();
            if (top.first == '(' && s[i] == ')') {
                count += 2;
                stk.pop();
            } else {
                pair<char, int> temp(s[i], count);
                stk.push(temp);
                continue;
            }
        }
        while (!stk.empty()) {
            pair<char, int> top = stk.top();
            if (top.second == count) {
                stk.pop();
                continue;
            }
            int temp = count - top.second;
            if (max < temp) max = temp;
            count -= temp;
            stk.pop();
        }
        if (max < count) max = count;
        return max;
    }
};

Improvement

精简代码

LeetCode 讨论区发现，许多解答思路与我的思路是一样的，但我的代码显得有些冗余了，附上精简后的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int maxL = 0, temp = 0;
        for (int i = 0; i < s.size(); ++i) {
            temp = stk.top();
            if (temp != -1 && s[i] == ')' && s[temp] == '(') {
                stk.pop();
                maxL = max(maxL, i - stk.top());
            } else stk.push(i);
        }
        return maxL;
    }
};

动态规划

还有用使用动态规划（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) {
        int *V = new int[s.length()];
        int open = 0, max = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') ++open;
            if (s[i] == ')' && open > 0) {
                // matches found
                V[i] = V[i - 1] + 2;

                // add matches from previous
                if (i - V[i] > 0) V[i] += V[i - V[i]];

                --open;
            }
            if (V[i] > max) max = V[i];
        }
        delete V;
        return max;
    }
};