日期：2026年10月4日
LeetCode 題目連結：678. Valid Parenthesis String
解題想法
中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, *, )$，其中 $*$ 可以當作 $($、$)$ 或空字串，要檢查 $s$ 之中的括號是否成對。這題下方的提示 1 是用遞迴與回溯窮舉將 $*$ 當作 $($、$)$ 或空字串所有可能的組合，但這個寫法的時間複雜度比較高，先不考慮。提示 2 是用動態規畫解題，用 $dp[i][j]$ 代表子字串 $s[i : j+1]$ 是否合法，寫法比較複雜，先不考慮。提示 3 是用堆疊記錄括號，討論區當中看起來最多人採用的是堆疊的寫法，看起來最可行。
我是用兩個堆疊 $left$、$star$，分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$，接下來分成 3 個狀況：
- $c == '('$，$i$ 推入 $left$。
- $c == '*'$，$i$ 推入 $star$。
- $c == ')'$，優先使用 $($ 配對，如果有 $left$ 有資料，移除 $left$ 最後一項。如果沒有 $($ 可以配對，再用 $*$ 配對，如果 $star$ 有資料，移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對，回傳 Fasle。
這題還有一個最極致的寫法，只用兩個整數變數 min_open、max_open，分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，接下來分成 3 個狀況：
- $c == '('$，min_open 加 1，max_open 加 1。
- $c == '*'$，$*$ 當作 $)$，min_open 減 1；$*$ 當作 $($，max_open 加 1。
- $c == ')'$，min_open 減 1，max_open 減 1。
Python 程式碼
Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 28.53%.
class Solution:
def checkValidString(self, s: str) -> bool:
n = len(s) # 長度
left = [] # 左括號於 s 之中的索引值
star = [] # 星號於 s 之中的索引值
for i in range(n):
c = s[i]
if c == '(': # 左括號，i 推入 left
left.append(i)
elif c == '*': # 星號，i 推入 star
star.append(i)
else: # 右括號，優先配對左括號
if left: # 有左括號能配對，移除 left 最後一項
left.pop()
elif star: # 有星號能配對，移除 star 最後一項
star.pop()
else: # 沒有左括號或星號能配對，回傳 False
return False
while left: # 處理剩下的左括號，取右側的星號配對
if star and star[-1] > left[-1]:
left.pop()
star.pop()
else: # 沒有可以配對的星號，回傳 False
return False
# 跑完上面的 while 迴圈時 left 已經清空，* 可以是空字串，star 不需要清空
return True
