題目出處
難度
medium
題目分類
String, Dynamic Programming, Stack, Greedy, Bracket Sequences
2026-10-06 一刷
個人範例程式碼 - 一刷 (2026/10/06)
class Solution:
def checkValidString(self, s: str) -> bool:
low = high = 0
for c in s:
if c == '(':
low += 1
high += 1
elif c == ')':
low -= 1
high -= 1
else:
low -= 1
high += 1
if high < 0: # 表示 * 全換 ( 也不夠用
return False
low = max(0, low) # low 不可為負，如果出現那必須為 ""
# 最終結算 low 必須為 0，否則有多的 (
return low == 0
算法說明
透過紀錄「儲存左括弧」的可能數量上下界，來判斷最後是否合法
( 與 ) 會讓上下界一起 +1 / -1
- 可以代表
- ( : 「儲存左括弧」的可能數量 上界 + 1 high
- ) : 「儲存左括弧」的可能數量 下界 - 1 low
- "" 直接視為不存在，上下界不動 +- 0
其他過程中的處理：
- high 過程中不可以 < 0：表示 * 全換 ( 也不夠處理過多的 )
- low 過程中最低只能是 0：* 換太多的 )，最低只能 0，其他需要換成空白
結尾處理：
必須 low == 0，不然表示有多餘無法處理的 (
Time Complexity
O(n)
Space Complexity
O(1)