題目描述
給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s，確定輸入字串是否有效。
- 左括號必須由相同類型的括號封閉。
- 左括號必須以正確的順序關閉。
- 每個右括號都有一個對應的相同類型的左括號。
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） 資料結構來模擬括號的開啟和閉合過程。當遍歷字串時：
- 如果遇到左括號，則將其推入堆疊。
- 如果遇到右括號，則檢查堆疊頂部是否是匹配的左括號：
- 如果匹配，將堆疊頂部彈出；
- 如果不匹配或堆疊為空，則返回 false。
- 最後，檢查堆疊是否為空，若是空則括號匹配有效，否則無效。
解法一：堆疊法
實現步驟
- 使用一個堆疊存儲遇到的左括號。
- 使用字典定義每種右括號與左括號的匹配關係。
- 遍歷字串：
- 如果是左括號，將其推入堆疊；
- 如果是右括號，檢查堆疊頂部是否匹配：若匹配，彈出堆疊頂部；若不匹配或堆疊為空，返回 false。
- 最後檢查堆疊是否為空。
程式碼實現 (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 標籤匹配、數學運算中的括號匹配等情境。