Valid Parentheses 解題教學:3 種解法完整比較|LeetCode 20 Best Practice

Valid Parentheses 解題教學示意圖|LeetCode 20

本文完整拆解 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:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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 <= 104
  • s consists 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 演算法步驟

  1. 建立空堆疊,以及一張右括號對應左括號的映射表。
  2. 逐一走訪字串中的每個字元。
  3. 若是左括號就推入堆疊;若是右括號,檢查堆疊是否為空或頂端不匹配,兩者任一成立就回傳 false。
  4. 走訪結束後,堆疊必須為空才回傳 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)本文採用,標準解