题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题思路一：
对于这种括号匹配问题，一般都是使用栈。
时间复杂度为：O(n)。
空间复杂度为：O(n)。
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s: return 0
res = 0
stack = [-1]
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
res = max(res, i - stack[-1])
return res
1、特判，若s为空，返回0
2、初试化栈stack=[-1]，和结果res=0。栈中元素表示上一不匹配位置索引。
3、遍历s：
若s[i]=="("，将当前位置索引加入stack。表示将当前左括号需要匹配，为不匹配索引。
若s[i]==")"：
1）出栈，stack.pop()。表示将对应左括号索引出栈，或者当栈中只有)时，将上一)索引出栈。
2）若栈为空，表示之前的所有的(匹配成功，上一步出栈的是栈底的-1或者是前一个不匹配的)。则更新栈底为当前")"的索引，表示不匹配的位置。
3）否则，说明和栈中的(匹配上了，此时更新最长序列res=max(res,i-stack[-1])。表示当前位置索引减去上一不匹配位置索引 和之前res中的较大值。
4更新res
解题思路二：动态规划算法方法
我们用 dp[i] 表示以 i 结尾的最长有效括号；
1、当 s[i] 为 (,dp[i] 必然等于 0，因为不可能组成有效的括号；
2、那么 s[i] 为 )时，当 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]；
时间复杂度：O(n)。
class Solution(object):
def longestValidParentheses(self, s):
length = len(s)
if length == 0:
return 0
dp = [0] * length
for i in range(1,length):
#当遇到右括号时，尝试向前匹配左括号
if s[i] == ')':
pre = i - dp[i-1] -1;
#如果是左括号，则更新匹配长度
if pre>=0 and s[pre] == '(':
dp[i] = dp[i-1] + 2
#处理独立的括号对的情形 类似()()、()(())
if pre>0:
dp[i] += dp[pre-1]
return max(dp);
网友评论