本文主要是介绍最长有效括号 - LeetCode 热题 90,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
大家好!我是曾续缘🤪
今天是《LeetCode 热题 100》系列
发车第 90 天
动态规划第 10 题
❤️点赞 👍 收藏 ⭐再看,养成习惯
最长有效括号 给你一个只包含
'('
和')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。难度:💝💝💝示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"示例 3:
输入:s = "" 输出:0提示:
0 <= s.length <= 3 * 104
s[i]
为'('
或')'
解题方法
- 使用一个数组
f
记录以每个字符结尾的最长有效括号子串的长度。 - 遍历字符串
s
,对于每个位置i
,我们尝试更新f[i]
。 - 如果
s[i]
是')'
,我们需要考虑两个情况:- 如果
s[i - 1]
是'('
,那么当前的')'
可以和i - 1
位置的'('
配对,这时候我们需要查看i - 2
位置的有效括号长度(如果i - 2
在数组范围内),然后加上当前的2
(因为包含当前的')'
)。 - 如果
i - f[i - 1] > 0
并且s[i - f[i - 1] - 1]
是'('
,那么当前的')'
可以和i - f[i - 1] - 1
位置的'('
配对,这时候我们需要更新f[i]
为f[i - 1] + 2 + (i - f[i - 1] - 2 >= 0 ? f[i - f[i - 1] - 2] : 0)
。
- 如果
Code
class Solution {public int longestValidParentheses(String s) {int n = s.length();int[] f = new int[n];for(int i = 1; i < n; i++){if(s.charAt(i) == ')'){if(s.charAt(i - 1) == '('){f[i] = (i >= 2 ? f[i - 2] : 0) + 2;}else if(i - f[i - 1] > 0 && s.charAt(i - f[i - 1] - 1) == '('){f[i] = f[i - 1] + ((i - f[i - 1]) >= 2 ? f[i - f[i - 1] - 2] : 0) + 2;}}}int ans = 0;for(int x : f){ans = Math.max(ans, x);}return ans;}
}
这篇关于最长有效括号 - LeetCode 热题 90的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!