32. Longest Valid Parentheses
2019-10-26 本文已影响0人
葡萄肉多
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
题意
给一个只包含"("和")"一堆括号的字符串，然后返回最长的合法的括号的长度。
思路
- 栈
从左到右扫描字符串，栈顶保存当前扫描的时候，合法序列前的一个位置的位置下标是多少。
如果扫描到"("，它的下标就入栈；
如果扫描到")"，就将栈顶出栈（代表栈顶的左括号匹配到了右括号），然后分两种情况：
- 此时栈不空
那么就用当前的位置减去栈顶的存的位置，然后就得到当前合法序列的长度，然后更新一下最长长度。 - 此时栈是空的
说明之前没有与之匹配的"("，那么就将当前的位置入栈。
class Solution:
def longestValidParentheses1(self, s):
stack = [-1]
count = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
count = max(count, i - stack[-1])
return count
- 动态规划
长度为len(s)的数组dp维护下标以i结尾的合法序列的最长长度。
遍历s，当字符为")"时，分两种情况：
- ")"的前一个字符为"("，类似于"()"
dp[i] = dp[i-2] + 2，如果i>=2，否则 dp[i] = 2 (前一个合法序列的长度，加上当前新增的长度 2） - ")"的前一个字符为")"，类似于"))"
需要判断 i - dp[i - 1] - 1 （前一个合法序列的前边一个位置） 是不是"("。
如果是左括号，则 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 （当前位置的前一个合法序列的长度，加上匹配的左括号前边的合法序列的长度，加上新增的长度 2）
如果不是，则dp[i] = 0，不用更新。
def longestValidParentheses2(self, s):
dp = [0]*len(s)
count = 0
for i in range(1, len(s)):
if s[i] == ')':
if s[i-1] == '(':
dp[i] = dp[i-2] + 2 if i >= 2 else 2
elif i-dp[i-1] > 0 and s[i-dp[i-1]-1] == "(":
dp[i] = dp[i-1] + (dp[i-dp[i-1]-2] if (i - dp[i-1]) >= 2 else 0) + 2
count = max(count, dp[i])
return count
- 计数
从左往右扫描，left 保存 "("的个数，right 保存")"的个数。
如果left==right，更新最大序列长度；
如果left>right，继续向右扫描；
如果left<right，则把left和right归零。
因为存在"((())"的情况，所以从右向左再扫描一遍。
def longestValidParentheses3(self, s):
left = 0
right = 0
count = 0
for i in range(len(s)):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
count = max(count, 2*right)
elif right > left:
left = 0
right = 0
left = 0
right = 0
for i in range(len(s)-1, -1, -1):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
count = max(count, 2* left)
elif left > right:
left = 0
right = 0
return count
