Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：20. Valid Parentheses（有效的括號）

深入理解堆疊資料結構在括號匹配中的應用

luk 收錄於 Leetcode
 約 800 字 預計閱讀 4 分鐘 

題目描述

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s，判斷字串是否有效。

有效字串需滿足：

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

範例

範例 1：

輸入：s = "()"
輸出：true

範例 2：

輸入：s = "()[]{}"
輸出：true

範例 3：

輸入：s = "(]"
輸出：false

範例 4：

輸入：s = "([)]"
輸出：false
解釋：雖然有對應的括號，但順序不正確

範例 5：

輸入：s = "{[]}"
輸出：true

限制條件

  • 1 <= s.length <= 10⁴
  • s 僅由括號 '()[]{}' 組成

核心概念：為什麼要用堆疊？

括號匹配的本質

觀察有效的括號序列，你會發現一個規律：最後出現的左括號，必須最先被匹配。

範例：{[()]}
     ↓
遇到 { → 需要找 }
遇到 [ → 需要找 ]（但要先處理）
遇到 ( → 需要找 )（但要先處理）
遇到 ) → 匹配最近的 (
遇到 ] → 匹配最近的 [
遇到 } → 匹配最近的 {

這正是**後進先出（LIFO）**的特性，而堆疊就是為此而生！

堆疊的視覺化

想像堆疊就像：

  • 一疊盤子：最後放上去的必須最先拿走
  • 瀏覽器的返回按鈕：最後訪問的頁面最先返回
  • 穿衣服和脫衣服：最後穿的最先脫

解法一：使用堆疊（最優解）

思路

  1. 遇到左括號，壓入堆疊
  2. 遇到右括號，檢查堆疊頂部是否為對應的左括號
  3. 最後檢查堆疊是否為空

程式碼實現 

class Solution:
    def isValid(self, s: str) -> bool:
        # 建立括號配對的映射
        bracket_map = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        
        # 初始化堆疊
        stack = []
        
        # 遍歷每個字符
        for char in s:
            if char in bracket_map:  # 如果是右括號
                # 檢查堆疊是否為空，或頂部元素是否匹配
                if not stack or stack[-1] != bracket_map[char]:
                    return False
                stack.pop()  # 匹配成功，彈出左括號
            else:  # 如果是左括號
                stack.append(char)
        
        # 所有括號都應該被匹配，堆疊應為空
        return len(stack) == 0

執行過程視覺化

讓我們詳細追蹤 s = "{[()]}"：

步驟 1：遇到 '{'
stack: ['{']
動作：壓入堆疊

步驟 2：遇到 '['
stack: ['{', '[']
動作：壓入堆疊

步驟 3：遇到 '('
stack: ['{', '[', '(']
動作：壓入堆疊

步驟 4：遇到 ')'
stack: ['{', '[', '(']
檢查：stack[-1] = '(' = bracket_map[')'] ✓
動作：彈出 '('
stack: ['{', '[']

步驟 5：遇到 ']'
stack: ['{', '[']
檢查：stack[-1] = '[' = bracket_map[']'] ✓
動作：彈出 '['
stack: ['{']

步驟 6：遇到 '}'
stack: ['{']
檢查：stack[-1] = '{' = bracket_map['}'] ✓
動作：彈出 '{'
stack: []

結果：stack 為空，返回 true

無效範例：s = "([)]" 

步驟 1-3：壓入 '(', '[', ')'
stack: ['(', '[']

步驟 4：遇到 ']'
stack: ['(', '[']
檢查：stack[-1] = '[' = bracket_map[']'] ✓
動作：彈出 '['
stack: ['(']

步驟 5：遇到 ')'
stack: ['(']
檢查：stack[-1] = '(' = bracket_map[')'] ✓
動作：彈出 '('
stack: []

等等...這樣看起來是有效的？讓我們重新分析！

正確分析 "([)]" 

實際上 s = "([)]" 的執行過程：

步驟 1：遇到 '(' → stack: ['(']
步驟 2：遇到 '[' → stack: ['(', '[']
步驟 3：遇到 ')' 
檢查：需要 '('，但 stack[-1] = '[' ✗
返回 False

複雜度分析

  • 時間複雜度：O(n)，其中 n 是字串長度
  • 空間複雜度：O(n)，最壞情況下（全是左括號）需要存儲 n 個字符

解法二：優化版本（使用字典簡化）

思路

將所有括號對存在字典中，讓程式碼更簡潔。

程式碼實現 

class Solution:
    def isValid(self, s: str) -> bool:
        # 更完整的映射（包含左右括號）
        pairs = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        
        stack = []
        
        for char in s:
            if char in pairs:  # 左括號
                stack.append(char)
            else:  # 右括號
                if not stack or pairs[stack.pop()] != char:
                    return False
        
        return len(stack) == 0

解法三：使用字串替換（不推薦但有趣）

思路

不斷替換掉有效的括號對，直到無法替換。

程式碼實現 

class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        
        return s == ''

執行範例 

s = "{[]}"
第 1 輪：替換 '[]' → s = "{}"
第 2 輪：替換 '{}' → s = ""
結果：返回 true

s = "([)]"
第 1 輪：沒有相鄰的配對括號
結果：返回 false

為什麼不推薦？

  • 時間複雜度：O(n²)，因為每次替換都要掃描整個字串
  • 空間複雜度：O(n)，需要創建新字串
  • 效率低下：相比堆疊解法慢很多

常見錯誤與陷阱

錯誤 1：忘記檢查堆疊是否為空 

# 錯誤示範
def isValid(self, s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in bracket_map:
            if stack[-1] != bracket_map[char]:  # 忘記檢查 stack 是否為空！
                return False
            stack.pop()
        else:
            stack.append(char)
    
    return len(stack) == 0

# 測試案例 s = ")" 會造成 IndexError

錯誤 2：忘記最後檢查堆疊 

# 錯誤示範
def isValid(self, s: str) -> bool:
    # ... 前面的程式碼 ...
    
    for char in s:
        # ... 處理邏輯 ...
    
    return True  # 錯誤！應該檢查 stack 是否為空

# 測試案例 s = "(" 會錯誤地返回 True

錯誤 3：括號類型混淆 

# 容易出錯的寫法
if char == ')' or char == '}' or char == ']':
    # 處理右括號

# 更好的寫法
if char in bracket_map:  # bracket_map 包含所有右括號
    # 處理右括號

進階思考

1. 如果允許其他字符怎麼辦？ 

def isValid(self, s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':  # 左括號
            stack.append(char)
        elif char in ')}]':  # 右括號
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
        # 其他字符直接忽略
    
    return len(stack) == 0

2. 如果要返回無效的位置？ 

def findInvalidPosition(self, s: str) -> int:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for i, char in enumerate(s):
        if char in bracket_map:
            if not stack or stack[-1][0] != bracket_map[char]:
                return i  # 返回無效右括號的位置
            stack.pop()
        else:
            stack.append((char, i))
    
    # 如果還有未匹配的左括號
    if stack:
        return stack[0][1]  # 返回第一個未匹配左括號的位置
    
    return -1  # 全部有效

3. 計算需要添加多少括號使其有效？

這是 LeetCode 921 題的變形，可以分別計算未匹配的左右括號數量。

效能優化技巧

1. 提前終止 

def isValid(self, s: str) -> bool:
    # 奇數長度不可能有效
    if len(s) % 2 == 1:
        return False
    
    # ... 其餘邏輯

2. 使用 collections.deque

對於大量操作，deque 的效能可能更好：

from collections import deque

def isValid(self, s: str) -> bool:
    stack = deque()
    # ... 使用 stack.append() 和 stack.pop()

相關題目

  1. LeetCode 22: Generate Parentheses - 生成有效括號組合
  2. LeetCode 32: Longest Valid Parentheses - 最長有效括號子串
  3. LeetCode 921: Minimum Add to Make Parentheses Valid - 使括號有效的最少添加
  4. LeetCode 1249: Minimum Remove to Make Valid Parentheses - 移除無效的括號

總結

這道題是堆疊應用的經典範例，掌握它你將學會：

  1. 堆疊的基本操作：push、pop、peek、isEmpty
  2. 括號匹配的思維：後進先出的應用
  3. 邊界條件處理：空堆疊、剩餘元素的檢查
  4. 程式碼優化技巧：使用映射表簡化邏輯

記住核心概念：遇到左括號就壓入，遇到右括號就匹配，最後檢查是否清空。

練習建議

  1. 先手動模擬幾個範例，理解堆疊的運作
  2. 嘗試不看答案寫出基本版本
  3. 思考各種邊界情況（空字串、全左括號、全右括號）
  4. 挑戰進階變形題目，加深理解
更新於 2024-12-20 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmStackString
返回 | 主頁
0%