題目目錄Valid Parenthesis String

不用猜每個 * 是什麼，只追蹤未配對 ( 的數量可能落在哪個範圍。

TIME O(n)空間 O(1)：只留 lo、hi

01 / 未配對 ( 的可能範圍INITIALIZE

i—

c—

lo—

hi—

可能的數量—

範圍通道格子＝讀完該字元後未配對 ( 的可能數量；紅色地板以下不合法

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：lo 和 hi 代表什麼？

把所有 * 的選法一次考慮，只記住範圍的兩端。

掃描時記錄「目前還沒配對的 ( 有幾個」。因為 * 可以當 (、) 或空字串，這個數量不是一個值，而是一群可能的值。

lo：所有合法選法中，未配對 ( 的最少數量。 hi：最多數量。中間每個整數都做得到，所以只要記兩端。

( 讓整段 +1，) 讓整段 −1，* 讓下緣 −1、上緣 +1。

hi < 0：連最多的可能都變負，代表 ) 已經多到怎麼選都配不完，直接回傳 False。

lo = max(lo, 0)：數量 −1 的那些選法讓某個 ) 找不到對象，是不合法的選法，刪掉它們，下緣回到 0。

最後 lo == 0 表示 0 在範圍裡：存在一種選法剛好全部配完。時間 O(n)，空間 O(1)。