凌云的博客

LeetCode 算法题 32. 最长有效括号

分类：algorithm| 发布时间：2016-09-24 14:07:00

---

题目

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解法 1，使用 stack

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                if (stk.empty()) continue;
                int k = stk.top();
                stk.pop();
                s[k] = '*';
                s[i] = '*';
            }
        }

        int maxLen = 0, i = 0, j = 0, N = s.size();
        while(i<N) {
            while (i < N && s[i] != '*') i++;
            j = i;
            while (j < N && s[j] == '*') j++;
            maxLen = max(maxLen,j-i);
            i = j;
        }

        return maxLen;
    }
};

解法 2，动态规划

• left：表示最近一个未匹配的左括号
• DP[i + 1]：表示下标为 i 的最长的匹配括号长度

当我们遇到一个 ')' 并且还有未被匹配的 '(' 时，根据上一个 DP 值将长度增加 2。 重点在于我们得到的长度可能不是最终的值。

比如： '(()())'，需要注意的是 DP 的下标从 1 开始而不是 0。

假设我们遇到了第二个 ')'，DP[5] = DP[4] + 2 = 0 + 2 = 2。 现在我们需要返回第一个 ')' 检查这里是否有匹配的字符串。 如果有则将其加起来： DP[5] += DP[5 - DP[5]]，即 DP[5] += DP[5 - 2]，最终 DP[5] = 4。

class Solution {
public:
    int longestValidParentheses(string s) {
        const int size = s.size();
        vector<int> DP(size + 1, 0);
        int left = 0, longest = 0;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '(') {
                left++;
            } else if (s[i] == ')' && left > 0) {
                DP[i + 1] = DP[i] + 2;
                DP[i + 1] += DP[i + 1 - DP[i + 1]];
                left--;
            }

            longest = max(longest, DP[i + 1]);
        }

        return longest;
    }
};