当前位置: 首页> 房产> 建筑 > 合肥网站建设兼职_网页设计你若安好便是晴天作业_如何做网站搜索引擎优化_数据分析师证书

合肥网站建设兼职_网页设计你若安好便是晴天作业_如何做网站搜索引擎优化_数据分析师证书

时间:2025/7/10 3:35:20来源:https://blog.csdn.net/yyds133/article/details/145799262 浏览次数:0次
合肥网站建设兼职_网页设计你若安好便是晴天作业_如何做网站搜索引擎优化_数据分析师证书

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""
输出:0

提示:

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

思路:

        一个有效括号有一下三种情况:

((()))、()()()、()(())

假设子问题为:以s[i]为结尾的最长有效括号的长度为dp[i]

首先,最长有效括号不会以`(`结尾。所以当s[i]为(时,dp[i]=0

情况二:当s[i-1]为(时,此时dp[i]=dp[i-2]+2

情况一(为情况三的特殊情况):当s[i-1]为)时,此时检查s[i-dp[i-1]-1]是否是(,如果是则dp[i] = dp[i-1]+2

情况三:在情况二的基础上加dp[i-dp[i-1]-2]

代码如下:

class Solution:def longestValidParentheses(self, s: str) -> int:if len(s) == 0:return 0n = len(s)dp = [0] * nfor i in range(n):if s[i] == '(':continueif s[i-1] == '(':if i-2 >=0:dp[i] = dp[i-2] +2elif i-2==-1:dp[i] = 2else:if dp[i-1] != 0 and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1] =='(':dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]return max(dp)

关键字:合肥网站建设兼职_网页设计你若安好便是晴天作业_如何做网站搜索引擎优化_数据分析师证书

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: