题目
给定一个只包含 '('
和 ')'
的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为"()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为"()()"
链接(中文版):https://leetcode-cn.com/problems/longest-valid-parentheses
链接(英文版):https://leetcode.com/problems/longest-valid-parentheses
分析
有其他解法,这里只用DP算法。
用一个和s等长的数组V记录结果,其中V[i]表示以第i个字符为结尾的最长有效括号长度。
当s[i]==‘(’时,由于以左括号为结尾是无效的,因此V[i]是0。
当s[i]==')'时,分两种情况:
- 如果s[i-1]==‘(’,则和s[i]配对,那么以s[i]为结尾的最大有效长度就是2加上以s[i-2]为结尾的最大有效长度(注意越界判断)。
- 如果s[i-1]==‘)’,则需要再次往前找左括号,以便和s[i]配对,那么往前多少呢,如果以s[i-1]为结尾的最大有效长度是4,即V[i-1]=4,则说明我们应该往再前跳过4个字符,如果4个字符之前的字符s[i-1-4]不是左括号,则s[i]这个右括号是没法配对的,因此V[i]=0;如果s[i-1-4]是左括号,则和s[i]成功配对,此时的最长有效长度就是4+2+V[i-1-4-1](注意越界判断)。最后加的V[i-1-4-1]是以s[i-1-4-1]为结尾的最大有效长度,现在要和s[i-1-4]到s[i]这一段连到一起。
举例说明
输入s是"(())())",为了取消越界判断,我们在s前边加一个任意字符,比如#。即输入是"#(())())",长度是8。
初始化一个等长(长度是8)的全零列表V。以下每一步都要记录max_len,最后返回即可。
- 从脚标2开始判断,因为脚标0是#,不管脚标1是什么括号,以它为结尾的长度是1,因此V[1]=0;脚标2是(,以左括号为结尾,是无效的,因此V[2]=0还是全零,即V还是全零。
- 脚标3是),此时脚标3-1是(,可以配对,长度是2+V[3-2]=2,此时V=[0, 0, 0, 2, 0, 0, 0, 0]。
- 脚标4是),此时脚标4-1是),不可以配对,由于V[4-1]=2,则往前跳2个字符,s[4-1-2]是左括号,可以配对,最大有效长度是2+V[4-1]+V[4-1-2]=2+2+0=4,此时V=[0, 0, 0, 2, 4, 0, 0, 0]。
- 脚标5是(,V不变,还是[0, 0, 0, 2, 4, 0, 0, 0]
- 脚标6是),此时脚标6-1是(,可以配对,长度是2+V[6-2]=6,此时V=[0, 0, 0, 2, 4, 0, 6, 0]。
- 脚标7是),此时脚标7-1是),不可以配对,由于V[7-1]=6,则往前跳6个字符,是#,不可以配对,因此V[7]=0,V不变。
代码
class Solution:
def longestValidParentheses(self, s: str) -> int:
s = '#' + s
V = [0] * len(s)
ret = 0 #最终的最大有效长度
for i in range(2, len(s)): #从2开始遍历,因为前边加了#
if s[i] == ')': #只需要处理是右括号的情况,因为以左括号为结尾是无效的序列
if s[i-1] == '(': #前边是左括号,可以配对
V[i] = V[i-2] + 2
else: #前边是右括号,只能再往前寻找左括号
idx = i - 1 - V[i-1] #再次往前跳过V[i-1]个字符
if s[idx] == '(':
V[i] = V[i-1] + 2 + V[idx-1]
if ret < V[i]:
ret = V[i]
# print(V)
# print(ret)
return ret
总结
提交结果,运行时间统计得不是很准确: