本文完整拆解 LeetCode 20 Valid Parentheses 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Valid Parentheses 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Python
# time complexity: O(n)
# space complexity: O(n)
class Solution:
def isValid(self, s: str) -> bool:
bracketMap = {"(": ")", "[": "]", "{": "}"}
openSet = set(["(", "[", "{"])
stack = []
for char in s:
if char in openSet:
stack.append(char)
elif stack and char == bracketMap[stack[-1]]:
stack.pop()
else:
return False
return stack == []
Input = "(())"
print(Solution().isValid(Input))
Valid Parentheses 解題思路
括號配對是堆疊的教科書範例。關鍵觀察是「最近開啟的括號必須最先被關閉」,這正是後進先出的語意。遇到左括號就推入堆疊,遇到右括號就檢查堆疊頂端是不是對應的左括號,是就彈出,不是就立刻判定失敗。
Valid Parentheses 演算法步驟
- 建立空堆疊,以及一張右括號對應左括號的映射表。
- 逐一走訪字串中的每個字元。
- 若是左括號就推入堆疊;若是右括號,檢查堆疊是否為空或頂端不匹配,兩者任一成立就回傳 false。
- 走訪結束後,堆疊必須為空才回傳 true。
Valid Parentheses 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(n) |
| 空間複雜度 | O(n) |
每個字元最多被推入與彈出各一次,時間為 O(n)。最壞情況(全部是左括號)堆疊會存下 n 個字元,空間為 O(n)。
Valid Parentheses 的邊界情況與常見錯誤
- 字串長度為奇數時不可能平衡,可以提早回傳 false。
- 走完之後忘了檢查堆疊是否為空,會把 “(((” 誤判為合法。
- 遇到右括號但堆疊已空,代表沒有對應的左括號,要立刻失敗。
- 若字串可能混入其他字元,要先決定是忽略還是視為非法。
Valid Parentheses 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 反覆用字串取代移除成對括號 | O(n²) | O(n) | 寫法短但效率差 |
| 計數器(只在單一種括號時可行) | O(n) | O(1) | 無法處理多種括號交錯 |
| 堆疊配對 | O(n) | O(n) | 本文採用,標準解 |
