2d23292e124c7663ee34f06af8b5fdd7
(难度Hard)Problem 32. Longest Valid Parentheses(最长匹配括号)

链接

Longest Valid Parentheses - LeetCode

难度等级

Hard

题干

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

题意

给定一个只包含左括号和右括号的字符串,要求返回能够匹配合法匹配的最长字符串的长度。

样例

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

题解

这道题是hard难度,的确不简单,比较巧妙。

我们先分析一下题目,题目要求返回合法的最长括号的长度。最简单的方法当然还是暴力,很容易想到暴力的解法。

解法一 暴力

暴力的方法很简单,我们枚举所有的可能组成合法括号串的开头,然后查看一下从该位置开始能够延伸的最长的合法串的长度。

当然我们知道,只有(才可以作为合法串的开头,)开头是一定不满足条件的。

所以暴力方法的伪代码就是:

def brute_force(s):
    for i in range(len):
        if s[i] == '(':
            l = r = 0
            for j in range(i, len):
                if s[j] == '(':
                    l++
                else:
                    r++
                if r > l:
                    break
                if r == l:
                    ans = max(ans, 2 * r)
    return ans

在之前判断括号是否合法的题目当中我们已经知道,当右括号的数量超过左括号的时候就表示再也不可能构成合法串了。所以我们只需要维护左右括号的数量,然后判断是否遇到了不合法的情况。只要没有遇到不合法的情况,并且左右括号的数量相等,就说明这一串括号是合法的。

解法二 dp

在看到这道题的时候,我就有一种感觉,这是一个动态规划问题。

不扯什么动态转移方程,不聊什么最优子结构,就说一点,就是这是一个看起来就很适合“肢解”的问题。由一个很大的问题,肢解成很多很小的部分。

那么怎么肢解呢?我们可以来试着推导一下。

假设dp[i]存的是以i结尾的构成的最长合法串的长度,那么显然,对于所有的’(‘,dp[i]一定是0。因为’(‘结尾构不成合法串。

如果s[i]是’)’呢?

很明显如果s[i-1]是’(‘,那么它们就可以构成一个组合。很明显,在这种情况下,dp[i] = dp[i-2] + 2

那如果s[i-1]也是’)’呢?很多人推到这里就停住了,不知道怎么办了。但其实,我们已经有了dp[i-1]了,那么我们就可以把s[i-1]构成的组合全部去掉。也就是说我们判断s[i-dp[i-1]-1]是不是一个’(‘,如果是,说明它可以和s[i]组成配对。

那组成配对之后呢?dp[i] = dp[i-dp[i-1]-2]+ dp[i-1] + 2

我们只需要在计算出每个dp[i]的时候,存储一下最大值就可以获取最终的答案了。

使用dp可以完全摆脱遍历起始位置的困扰,并且编码复杂度也并不大。

附上代码:

top Created with Sketch.