LeetCode 筆記 - 32. Longest Valid Parentheses

題目在此 32. Longest Valid Parentheses

給定一個只有一種括號的字串,請找出最長的合法括號字串長度

解題思維

如果沒解過這題,可以先看看 LeetCode 筆記 - 20. Valid Parentheses

這題一樣會用到 Stack 來處理這個問題

基本的思維是如果遇到左邊括號,那就放一個 0 進 Stack,因為尚未配對成功
如果遇到右邊括號,而且 Stack 長度大於 1,表示可以配對成功
這時我們就把最後一個數字 pop 出來 + 2,再跟 Stack 最後一個數字相加
這個動作等於是把目前的結果加總在之前結果裡

如果失敗了,那就將 Stack 清空

完成 😎

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def longestValidParentheses(self, s: str) -> int:

stack = [0]

result = 0
for c in s:
print(stack)
if c == '(':
stack.append(0)
elif len(stack) > 1:
# 表示可以配對成功
# 把之前成功的數字,放在前面結果的最後一個
val = stack.pop()
stack[-1] += val + 2

result = max(result, stack[-1])

else:
# fail point
stack = [0]

return result

也許你也會想看看