[LeetCode解題攻略] 20. Valid Parentheses

題目描述

給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s，確定輸入字串是否有效。

輸入字串在以下情況下有效：

1. 左括號必須由相同類型的括號封閉。
2. 左括號必須以正確的順序關閉。
3. 每個右括號都有一個對應的相同類型的左括號。

範例 1：

Input: s = "()"
Output: true

範例 2：

Input: s = "()[]{}"
Output: true

範例 3：

Input: s = "(]"
Output: false

範例 4：

Input: s = "([)]"
Output: false

範例 5：

Input: s = "([])"
Output: true

解題思路

此問題的核心在於檢查括號的匹配情況，適合使用 堆疊（Stack） 資料結構來模擬括號的開啟和閉合過程。當遍歷字串時：

1. 如果遇到左括號，則將其推入堆疊。
2. 如果遇到右括號，則檢查堆疊頂部是否是匹配的左括號：
3. • 如果匹配，將堆疊頂部彈出；
   • 如果不匹配或堆疊為空，則返回 false。
3. 最後，檢查堆疊是否為空，若是空則括號匹配有效，否則無效。

解法一：堆疊法

實現步驟

1. 使用一個堆疊存儲遇到的左括號。
2. 使用字典定義每種右括號與左括號的匹配關係。
3. 遍歷字串：
4. • 如果是左括號，將其推入堆疊；
   • 如果是右括號，檢查堆疊頂部是否匹配：若匹配，彈出堆疊頂部；若不匹配或堆疊為空，返回 false。
4. 最後檢查堆疊是否為空。

程式碼實現 (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        # 定義匹配關係的字典
        matching = {')': '(', '}': '{', ']': '['}
        stack = []

        for char in s:
            # 如果是右括號，檢查堆疊頂部是否匹配
            if char in matching:
                if stack and stack[-1] == matching[char]:
                    stack.pop()  # 匹配成功，彈出堆疊頂部
                else:
                    return False  # 匹配失敗
            else:
                # 如果是左括號，壓入堆疊
                stack.append(char)
        
        # 最後檢查堆疊是否為空
        return not stack

時間與空間複雜度

• 時間複雜度：O(n)，其中 n 是字串的長度，因為每個字元最多只會被處理一次。
• 空間複雜度：O(n)，最壞情況下堆疊需要存儲所有的左括號。

解法二：使用列表模擬堆疊

思路

與解法一類似，但通過提前檢查和縮減堆疊操作次數進行小幅度優化。

程式碼實現 (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        # 定義匹配關係
        matching = {')': '(', '}': '{', ']': '['}
        stack = []

        for char in s:
            # 如果是右括號且匹配失敗，直接返回 False
            if char in matching and (not stack or stack[-1] != matching[char]):
                return False
            elif char in matching:
                stack.pop()  # 匹配成功，彈出堆疊頂部
            else:
                stack.append(char)  # 左括號壓入堆疊
        
        # 如果堆疊為空，表示匹配成功
        return not stack

時間與空間複雜度

• 時間複雜度：O(n)，與解法一相同。
• 空間複雜度：O(n)，與解法一相同。

總結

該問題中，堆疊法是一個經典解法，這個題目經常被用於考察對堆疊的理解與操作熟練度。熟練掌握後，可應用於類似的問題，如處理 HTML 標籤匹配、數學運算中的括號匹配等情境。