Title

給定一個只包含 ‘(’ 和 ‘)’ 的字符串，找出最長的包含有效括號的子串的長度。

示例 1:

輸入: “(()”
輸出: 2
解釋: 最長有效括號子串為 “()”

示例 2:

輸入: “)()())”
輸出: 4
解釋: 最長有效括號子串為 “()()”

棧

Solve

括號匹配問題，第一個想到的數據結構就是棧，考慮到邊界情況，要保持棧底元素為當前已經遍歷過的元素中最后一個沒有被匹配的右括號的下標，初始情況放入-1，棧里其他元素維護左括號的下標。

具體過程：

• 如果遇到左括號，將其下標放入棧中
• 如果遇到右括號：
  • 如果棧為空，說明當前的右括號為沒有被匹配的右括號，我們將其下標放入棧中來更新我們之前提到的「最后一個沒有被匹配的右括號的下標」
  • 如果棧不為空，當前右括號的下標減去棧頂元素即為「以該右括號為結尾的最長有效括號的長度」

Code

def longestValidParentheses_stack(self, s: str) -> int:stack, ans = [-1], 0for i in range(len(s)):if s[i] == '(':stack.append(i)else:stack.pop()if not stack:stack.append(i)else:ans = max(ans, i - stack[-1])return ans

復雜度分析

時間復雜度： O(n)，n 是給定字符串的長度。我們只需要遍歷字符串一次即可。

空間復雜度： O(n)。棧的大小在最壞情況下會達到 n，因此空間復雜度為 O(n) 。

動態規劃

Solve

定義dp數組并全部初始化為0，dp[i]表示以下標i字符結尾的最長有效括號的長度。

有效子串一定以右括號結尾，所有以左括號結尾的子串對應的dp值必定為0。

從前往后遍歷字符串求解dp值，每兩個字符檢查一次：

s[i]=’)’，s[i-1]=’(’，可以推出：dp[i]=dp[i?2]+2

s[i]=’)’，s[i-1]=’)’，如果s[i?dp[i?1]?1]=’(’，可以推出：dp[i]=dp[i?1]+dp[i?dp[i?1]?2]+2

我們考慮如果倒數第二個 ‘)’ 是一個有效子字符串的一部分（記作 sub_s），對于最后一個 ‘)’ ，如果它是一個更長子字符串的一部分，那么它一定有一個對應的 ‘(’ ，且它的位置在倒數第二個 ‘)’ 所在的有效子字符串的前面（也就是 sub_s 的前面）。

因此，如果子字符串 sub_s 的前面恰好是 ‘(’ ，那么我們就用 2 加上 sub_s 的長度（dp[i?1]）去更新 dp[i]。同時，我們也會把有效子串 “(sub_s)” 之前的有效子串的長度也加上，也就是再加上 dp[i?dp[i?1]?2]。

最后的答案即為 dp 數組中的最大值。

Code

def longestValidParentheses_dp(self, s: str) -> int:length = len(s)if length == 0:return 0dp = [0] * lengthfor i in range(length):if s[i] == ')' and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2return max(dp)

復雜度分析

時間復雜度： O(n)，其中 n 為字符串的長度。我們只需遍歷整個字符串一次，即可將 dp 數組求出來。

空間復雜度： O(n)。我們需要一個大小為 n 的 dp 數組。

總結

以上是生活随笔為你收集整理的32. Longest Valid Parentheses 最长有效括号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。