YSMull
<-- Algorithm

Longest Valid Parentheses

原题链接

题目

求最长的有效括号的长度。题目对有效括号的定义没有说清楚,我以为是连续若干个(),实际上有效括号P的定义如下:

1. () is P
2. PP is P
3. (P) is P

求解

这道题分类在动态规划下面,我尝试做了一下没有做出来。然后看到讨论区的动态规划解法,觉得有点难想到。但是另一个使用栈的解法比较有意思。

使用栈解决

依次把括号的index入栈,如果遇到'('就push,如果遇到')'且栈顶是'('就pop,这样到最后,能匹配上的括号全部都出栈了,
在栈里剩下的括号是没有匹配到的。这里仔细看一下栈里面剩下的括号,可以发现有一个特点,它们是字符串里所有的连续有效括号的分隔点
每两个分割点之间一定是有效括号,我们遍历栈里剩下的元素,求出所有的有效括号的长度即可。

  str: )(()(())))()()   len:14
stack: ↑        ↑
分隔点: 0        9
int longestValidParentheses(string s) {
    stack<int> stack;
    int len = s.length();
    for (int i = 0; i < len; i ++) {
        if (s[i] == '(') {
            stack.push(i);
            continue;
        }
        if (!stack.empty() && s[stack.top()] == '(') {
            stack.pop();
        } else {
            stack.push(i);
        }
    }
    if (stack.empty()) return len;
    else {
        int maxNum = -1;
        int end = len;
        while(!stack.empty()) {
            int start = stack.top();
            stack.pop();
            maxNum = max(maxNum, end - start - 1);
            end = start;
        }
        maxNum = max(maxNum, end);// 这里容易漏掉,最后还要比较一次
        return maxNum;
    }
}

使用动态规划

思路来源自讨论区,不是很好想。

定义dp[i]是以第i个元素结尾的最长有效括号。

        ┏-0                             if str[i] == '('
dp[i] = ┠-dp[i-2] + 2                   if str[i] == ')' && str[i-1] == '('
        ┗-dp[i-1] + 2 + dp[i-dp[i-1]-2] if str[i] == ')' && str[i-1] == ')'


代码