32. 最长有效括号 栈 动态规划

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

解题思路

class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int 用栈模拟一遍，将匹配的括号的位置全部置1，经过处理后，此题变为寻找最长的连续的0的长度 """ if len(s)==0 or len(s)==1: return 0 # 能匹配的括号为0，不能匹配上的置为1 dp = [0] * len(s) # 保存左括号的索引 stack = [] for idx, num in enumerate(s): if num=='(': stack.append(idx) # 如果有能匹配上右括号的左括号 elif num==')' and stack!=[]: stack.pop() # 如果没有能匹配上右括号的左括号，将该处置为1 else: dp[idx] = 1 # 如果还剩下了没有匹配的左括号，将其置为1 while stack!=[]: dp[stack[-1]] = 1 stack.pop() max_len = 0 cnt = 0 # 找最长的连续为0 的长度 for i in range(len(s)): if dp[i]==1: cnt = 0 continue else: cnt += 1 max_len = max(cnt, max_len) return max_len class Solution: def longestValidParentheses(self, s: str) -> int: length = len(s) if length==0: return 0 # dp[i]表示以i结尾的最长有效括号长度 dp = [0] * length for i in range(1, length): # 如果是右括号，尝试向前匹配左括号 if s[i]==')': # 找到i前面的有效括号序列前的第一个括号 pre = i - dp[i-1] - 1 if pre>=0 and s[pre]=='(': # 如果能匹配上，则长度都加2 dp[i] = dp[i-1] + 2 # 如果前面还有括号，把前面的有效括号商都也添加进来 if pre>0: dp[i] += dp[pre-1] return max(dp)