解題說明
Valid Parenthesis String
題目描述：給定一個只包含 (、)、* 的字串 s，其中 * 可以被視為 (、) 或空字元。判斷字串是否為有效的括號字串。
解題思路：使用貪心策略，追蹤「目前可能的未配對左括號數量」的範圍 [lo, hi]。
lo：在最保守的假設下（*盡量視為)或空），未配對左括號的最小可能數量。hi：在最樂觀的假設下（*盡量視為(），未配對左括號的最大可能數量。
遍歷每個字元：
- 遇到
(：lo++，hi++（必定增加一個未配對左括號）。 - 遇到
)：lo--，hi--（必定消耗一個左括號，或讓計數減少）。 - 遇到
*：lo--（把*視為)），hi++（把*視為(）。
兩個關鍵約束：
- 若
hi < 0：即使最樂觀地將所有*視為(，右括號仍過多，字串必定無效，回傳false。 lo = max(lo, 0)：未配對左括號不可能為負數，若lo降到 0 以下就夾住為 0（即使保守地把*視為)也不強迫產生負數）。
最終判斷：若 lo == 0，表示存在一種 * 的解釋方式使所有括號完整配對，回傳 true。
C++ 解法
複雜度分析
時間複雜度：O(n) — 只需單次線性遍歷字串，每個字元做常數次操作。
空間複雜度：O(1) — 只使用兩個整數變數 lo 和 hi，不需要任何額外的堆疊或陣列。
虛擬碼
1. Initialize lo = 0, hi = 0.
2. For each character c in s:
a. If c == '(': lo++, hi++.
b. If c == ')': lo--, hi--.
c. If c == '*': lo--, hi++.
d. If hi < 0: return false (impossible to balance).
e. lo = max(lo, 0) (clamp lo to non-negative).
3. Return lo == 0.其他解法
動態規劃 O(n^2)：定義 dp[i][j] 為處理到第 i 個字元時，未配對左括號數量為 j 的可行性。每個字元根據其類型轉移狀態。時間與空間複雜度均為 O(n^2)，可行但效率低於貪心解法。
堆疊模擬 O(n)：分別維護兩個堆疊，一個存放 ( 的索引，一個存放 * 的索引。掃描時用 * 匹配多餘的 )，最後確認剩餘的 ( 能被 * 匹配（且 * 在 ( 右側）。邏輯正確但需要 O(n) 空間，不如貪心解法簡潔。
延伸思考
- 若
*只能被視為空字元（不能當括號），解法應如何簡化？ - 此題的貪心解法維護的是一個「可能值的區間」
[lo, hi]。思考這種「範圍貪心」思路還能應用在哪些類似的括號或字串驗證問題上？ - 如果字串中還包含第四種字元
?，它只能被視為(或)（不能為空），如何修改[lo, hi]的更新規則？