題目描述
給定一個只包含 '(' 和 ')' 的字串，找出其中包含的最長的有效括號子字串的長度。
範例1:Input: s = "(()"
Output: 2
Explanation: 最長的有效括號子字串是 "()"，長度為 2。
範例2:
Input: s = ")()())"
Output: 4
Explanation: 最長的有效括號子字串是 "()()"，長度為 4。
範例3:
Input: s = ""
Output: 0
解法一：使用堆疊 (Stack)
我們可以使用堆疊來追蹤括號的索引。堆疊的初始狀態是放入一個基準值 -1，用來計算有效括號的長度。
步驟
- 初始化一個空堆疊，並放入基準值
-1。 - 遍歷字串的每個字符：
- 如果是左括號
(，將其索引推入堆疊。 - 如果是右括號
)： - 從堆疊彈出一個元素（匹配到最近的左括號）。
- 如果堆疊為空，將當前索引推入堆疊作為新的基準。
- 如果堆疊不為空，計算當前索引與堆疊頂部索引之間的距離，更新最長有效括號長度。
- 如果是左括號
程式碼實現
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 為結尾的最長有效括號的長度。
步驟
- 初始化一個長度為
n的陣列dp，所有元素初始為0。 - 遍歷字串從第二個字符開始：
- 如果當前字符是右括號
)，檢查其前一字符： - 如果前一字符是左括號 (，則 dp[i] = dp[i-2] + 2。
- 如果前一字符是右括號，且在其有效括號前一位 i - dp[i-1] - 1 是左括號，則 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。
- 如果當前字符是右括號
- 返回
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)
我們可以使用雙指針分別從左到右和從右到左遍歷字串，計算有效括號的長度。
步驟
- 初始化兩個計數器
left和right，分別計算左括號和右括號的數量。 - 從左到右遍歷：
- 遇到左括號
(，增加left。 - 遇到右括號
)，增加right。 - 如果
left == right，計算當前有效括號長度。 - 如果
right > left，重置計數器。
- 遇到左括號
- 從右到左遍歷，類似操作，交換
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)，只使用了常數空間。
總結
- 堆疊法： 簡單直接，適合理解括號匹配的邏輯。
- 動態規劃： 使用額外的記憶體來存儲中間結果，計算最長有效括號。
- 雙指針法： 常數空間解法，效率較高。
根據實際需求選擇合適的解法。如果需要處理長度較大的字串且對空間要求較高，雙指針法是最佳選擇。
