LeetCode-32 New
摘要：
Longest Valid Parentheses
Given a string containing just the characters'('
and')'
, find the length of the longest valid...
Longest Valid Parentheses
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"()()"
Solution:
1.使用棧：
首先將-1放入棧中，然後每次遇到 '(' 就將其下標入棧，每遇到 ')' 就出棧，並計算當前有效的字串長度。當出棧後棧變為空，並將當前下標入棧。並保持記錄最長字串。
class Solution:
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
max_length = 0
stack = [-1]
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if len(stack) == 0:
stack.append(i)
else:
max_length = max(max_length, i - stack[-1])
return max_length
2.動態規劃：
宣告 dp 陣列，長度和字串總長度一致。dp 陣列的第 i 個元素代表以 i 結尾的最長子串的長度。初始 dp全為0。有效子串肯定是以 ')' 結尾，因此分為兩種情況：
- s[i] = ')' ands[i - 1] = '(' , 此時 dp[i] = dp[i - 2] + 2
- s[i] = ')' ands[i - 1] = ')' , 此時 dp[i] = dp[i - 1] +dp[i - dp[i-1] - 2] + 2
class Solution:
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
max_length = 0
dp = [0] * len(s)
for i in range(1, len(s)):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = (dp[i - 2] if i >= 2 else 0) + 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
max_length = max(max_length, dp[i])
return max_length