LeetCode 32 最长有效括号

Ciel Yang 收录于类别练习 OJ解题报告

2020-07-05 2020-07-05 约 1138 字预计阅读 3 分钟

本题由一道基本问题“括号匹配”改造而来，应当和原有问题的解题思路比对思考解法不同的原因，尤其是栈解法的实现细节。

题目描述

原题链接如下： LeetCode 32 最长有效括号

题目大意

字符串只包含 ‘(’ 和 ‘)’，答案是找出最长的包含有效括号的子串的长度。

注意：子串的各个字符必须互相连接。

输入与输出

示例输入为：

1
2
3
4
5
Input 1:
"(()"

Input 2:
")()())"

第一组数据的最长有效括号子串为 “()"，第二组数据的最长有效括号子串为 “()()"，所以对应输出为：

1
2
3
4
5
Output 1:
2

Output 2:
4

解题思路

“括号匹配”的基本思路就是使用辅助栈，较难的是使用动态规划的解法。

解法一：栈

基本的使用栈进行括号匹配时，只要有匹配就会进行弹出操作，但是原有的匹配操作只存储括号内容，无法计算子串长度。解决的方法也很简单，只要存储原字符串的各个字符的相应下标即可。同时，栈中相应的存储标准也要进行一定的修改，简单说就是存储“最后一个没有被匹配的右括号的下标”：

只要遇到 ‘(’，就把它的下标压入栈中
遇到 ‘)’ 时，先弹出栈顶的 ‘(’ 表示匹配成功，然后：
- 如果之后栈为空，说明之前不存在没有匹配的右括号，那就把它的下标存入栈中，作为新的“最后一个没有被匹配的右括号的下标”
- 如果栈不为空，则使用当前右括号下标减去栈顶元素，得到一个有效括号子串的长度

另外，还要注意特殊的边界条件，如果原字符串的开头就是一个有效子串，那么这个算法无法正确计算它的长度。修复的方法就是在最开始存入一个一个哨兵下标 -1，表示有一个虚拟的没有被匹配的右括号即可修复算法的 bug。

解法二：动态规划

类似的不定边界的子串问题，我们可以使用一种模板式的动态规划，即使用 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度，答案是 dp 数组的最大值。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。

初始的 dp 值很好确定，我们把数组值初始化为 0。然后，从前往后遍历填充 dp 数组的内容，分情况讨论确定递推公式：

s[i] 为 ‘)’ 且 s[i-1] 为 ‘(’ 时，有效字符串为 “…()” 的形式，递推公式为：$dp[i] = dp[i - 2] + 2$
s[i] 为 ‘)’ 且 s[i-1] 为 ‘)’ 时，如果 s[i-dp[i-1]-1] 存在且为 ‘(’，那么递推公式为：$dp[i] = dp[i - 1] + dp[i-dp[i-1]-2] + 2$

代码

解法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayDeque

class Solution {
    fun longestValidParentheses(s: String): Int {
        if (s.isEmpty()) return 0
        val stack = ArrayDeque<Int>()
        stack.push(-1)
        var re = 0
        for (i in s.indices) {
            if (s[i] == '(') stack.push(i)
            else {
                stack.pop()
                if (stack.isEmpty()) stack.push(i)
                else re = maxOf(re, i - stack.peek())
            }
        }

        return re
    }
}

解法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun longestValidParentheses(s: String): Int {
        val dp = IntArray(s.length)
        for (i in s.indices) {
            if (s[i] == '(' || i < 1) continue
            if (s[i - 1] == '(')
                dp[i] = 2 + if (i > 1) dp[i - 2] else 0
            else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                dp[i] = dp[i - 1] + 2 + if (i - dp[i - 1] >= 2) dp[i - dp[i - 1] - 2] else 0
        }
        return dp.max() ?: 0
    }
}

目录