LeetCode 筆記 - 32. Longest Valid Parentheses

Posted on

題目在此 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

相關文章