# LeetCode 32，并不Hard的难题，解法超级经典，带你领略动态规划的精彩

2019/04/10 10:10

<br>

<br>

### 链接

Longest Valid Parentheses

### 难度

<font color=red>Hard</font>

<br>

### 描述

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

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

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

<br>

<br>

<br>

## 暴力

<br>

``````def brute_force(s):
ans = 0
for i in range(len(s)):
if s[i] == '(':
l = r = 0
for j in range(i, len):
if s[j] == '(':
l++
else:
r++
# 如果已经不可能构成答案
if r > l:
break
if r == l:
ans = max(ans, 2 * r)
return ans
``````

<br>

## 寻找模式法

<br>

``````class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
l, r = 0, 0
# 正向遍历，寻找)t( 和 )t(两种情况
for i in range(n):
if s[i] == '(':
l += 1
else:
r += 1
if r > l:
l, r = 0, 0
elif r == l:
ans = max(ans, l + r)

l, r = 0, 0
# 反向遍历，寻找(t(这种情况
for i in range(n-1, -1, -1):
# 由于反向遍历，所以非法的判断条件和正向相反
if s[i] == '(':
l += 1
if l > r:
l, r = 0, 0
elif l == r:
ans = max(ans, l+r)
else:
r += 1
return ans
``````

<br>

## dp

<br>

``````s:    a       b    (    )     )
idx:  i-4    i-3   i-2  i-1   i
``````

``````class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
dp = [0 for _ in range(n)]
for i in range(1, n):
if s[i] == ')':
# 如果i-1是（，那么我们判断i-2
if s[i-1] == '(':
dp[i] = 2 + (dp[i-2] if i > 1 else 0)
# 如果i-1也是)，我们需要继续往前判断
# 这里要特别注意下下标， 很容易写错
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)

ans = max(ans, dp[i])
return ans
``````

0
0 收藏

0 评论
0 收藏
0