凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 32. Longest Valid Parentheses

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


题目

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,使用 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]]

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = (int)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;
    }
};