[LeetCode] 32. Longest Valid Parentheses @ python

本文主要是介绍[LeetCode] 32. Longest Valid Parentheses @ python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一．题目：
找出一个只包含"(“和”)"的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。
Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

二．解题思路：
求解符合要求的最大长度问题常用到动态规划．
dp[i] 表示以i为符合要求的子字符串末尾时的最大长度．
代码如下：

class Solution(object):def longestValidParentheses(self, s):""":type s: str:rtype: int"""if not s:return 0length = len(s)dp = [0 for __ in range(length)]  # [0,0,0,0,0,0]for i in range(1, length):if s[i] == ")":j = i - 1 - dp[i - 1]  if j >= 0 and s[j] == "(":  dp[i] = dp[i - 1] + 2if j - 1 >= 0:dp[i] += dp[j - 1]  return max(dp)

还有一种巧妙地解法，即利用栈存储不满足有效括号时的列表元素下标．
代码如下：

class Solution(object):def longestValidParentheses(self, s):""":type s: str:rtype: int"""#利用栈stack=[]for i in range (0, len(s)):#如果此时栈为空，则把当前符号的index压入栈中if not stack: stack.append(i)else:if s[i] ==")" and s[stack[-1]] == "(":stack.pop()continuestack.append(i)end = len(s)if not stack: return endres = 0while stack:start = stack.pop()res = max(res, end-start-1)end = startres = max(res, end)return res

这篇关于[LeetCode] 32. Longest Valid Parentheses @ python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---