[LeetCode解題攻略] 32. Longest Valid Parentheses

題目描述

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

範例1:

Input: s = "(()"
Output: 2
Explanation: 最長的有效括號子字串是 "()"，長度為 2。

範例2:

Input: s = ")()())"
Output: 4
Explanation: 最長的有效括號子字串是 "()()"，長度為 4。

範例3:

Input: s = ""
Output: 0

解法一：使用堆疊 (Stack)

我們可以使用堆疊來追蹤括號的索引。堆疊的初始狀態是放入一個基準值 -1，用來計算有效括號的長度。

步驟

1. 初始化一個空堆疊，並放入基準值 -1。
2. 遍歷字串的每個字符：
3. • 如果是左括號 (，將其索引推入堆疊。
   • 如果是右括號 )：
   • • 從堆疊彈出一個元素（匹配到最近的左括號）。
     • 如果堆疊為空，將當前索引推入堆疊作為新的基準。
     • 如果堆疊不為空，計算當前索引與堆疊頂部索引之間的距離，更新最長有效括號長度。

程式碼實現

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_length = 0

        for i, char in enumerate(s):
            if char == '(':  # 左括號
                stack.append(i)
            else:  # 右括號
                stack.pop()
                if not stack:  # 如果堆疊為空，更新基準索引
                    stack.append(i)
                else:  # 計算當前有效括號長度
                    max_length = max(max_length, i - stack[-1])

        return max_length

時間與空間複雜度

• 時間複雜度： O(n)，其中 n 是字串的長度。我們只需遍歷字串一次。
• 空間複雜度： O(n)，在最壞情況下堆疊可能存儲所有索引。

解法二：動態規劃 (Dynamic Programming)

動態規劃的思路是使用一個陣列 dp，其中 dp[i] 表示以下標 i 為結尾的最長有效括號的長度。

步驟

1. 初始化一個長度為 n 的陣列 dp，所有元素初始為 0。
2. 遍歷字串從第二個字符開始：
3. • 如果當前字符是右括號 )，檢查其前一字符：
   • • 如果前一字符是左括號 (，則 dp[i] = dp[i-2] + 2。
     • 如果前一字符是右括號，且在其有效括號前一位 i - dp[i-1] - 1 是左括號，則 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。
3. 返回 dp 陣列中的最大值。

程式碼實現

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        dp = [0] * n
        max_length = 0

        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = dp[i-2] + 2 if i >= 2 else 2
                elif i - dp[i-1] - 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 >= 0 else 0) + 2
                max_length = max(max_length, dp[i])

        return max_length

時間與空間複雜度

• 時間複雜度： O(n)，我們只需遍歷字串一次。
• 空間複雜度： O(n)，需要存儲長度為 n 的 dp 陣列。

解法三：雙指針法 (Two Pointers)

我們可以使用雙指針分別從左到右和從右到左遍歷字串，計算有效括號的長度。

步驟

1. 初始化兩個計數器 left 和 right，分別計算左括號和右括號的數量。
2. 從左到右遍歷：
3. • 遇到左括號 (，增加 left。
   • 遇到右括號 )，增加 right。
   • 如果 left == right，計算當前有效括號長度。
   • 如果 right > left，重置計數器。
3. 從右到左遍歷，類似操作，交換 left 和 right 的計算順序。

程式碼實現

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        left = right = max_length = 0

        # 從左到右遍歷
        for char in s:
            if char == '(':
                left += 1
            else:
                right += 1
            if left == right:
                max_length = max(max_length, 2 * right)
            elif right > left:
                left = right = 0

        left = right = 0

        # 從右到左遍歷
        for char in reversed(s):
            if char == ')':
                right += 1
            else:
                left += 1
            if left == right:
                max_length = max(max_length, 2 * left)
            elif left > right:
                left = right = 0

        return max_length

時間與空間複雜度

• 時間複雜度： O(n)，需要兩次遍歷字串。
• 空間複雜度： O(1)，只使用了常數空間。

總結

• 堆疊法： 簡單直接，適合理解括號匹配的邏輯。
• 動態規劃： 使用額外的記憶體來存儲中間結果，計算最長有效括號。
• 雙指針法： 常數空間解法，效率較高。

根據實際需求選擇合適的解法。如果需要處理長度較大的字串且對空間要求較高，雙指針法是最佳選擇。