LeetCode 32 最长有效括号
目录
本题由一道基本问题“括号匹配”改造而来,应当和原有问题的解题思路比对思考解法不同的原因,尤其是栈解法的实现细节。
题目描述
原题链接如下: LeetCode 32 最长有效括号
题目大意
字符串只包含 ‘(’ 和 ‘)’,答案是找出最长的包含有效括号的子串的长度。
注意:子串的各个字符必须互相连接。
输入与输出
示例输入为:
|
|
第一组数据的最长有效括号子串为 “()",第二组数据的最长有效括号子串为 “()()",所以对应输出为:
|
|
解题思路
“括号匹配”的基本思路就是使用辅助栈,较难的是使用动态规划的解法。
解法一:栈
基本的使用栈进行括号匹配时,只要有匹配就会进行弹出操作,但是原有的匹配操作只存储括号内容,无法计算子串长度。解决的方法也很简单,只要存储原字符串的各个字符的相应下标即可。同时,栈中相应的存储标准也要进行一定的修改,简单说就是存储“最后一个没有被匹配的右括号的下标”:
- 只要遇到 ‘(’,就把它的下标压入栈中
- 遇到 ‘)’ 时,先弹出栈顶的 ‘(’ 表示匹配成功,然后:
- 如果之后栈为空,说明之前不存在没有匹配的右括号,那就把它的下标存入栈中,作为新的“最后一个没有被匹配的右括号的下标”
- 如果栈不为空,则使用当前右括号下标减去栈顶元素,得到一个有效括号子串的长度
另外,还要注意特殊的边界条件,如果原字符串的开头就是一个有效子串,那么这个算法无法正确计算它的长度。修复的方法就是在最开始存入一个一个哨兵下标 -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$
代码
解法一:
|
|
解法二:
|
|