给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 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)