題目描述:給定一個只包含 (、)、* 的字串 s,其中 * 可以被視為 (、) 或空字元。判斷字串是否為有效的括號字串。
解題思路:使用貪心策略,追蹤「目前可能的未配對左括號數量」的範圍 [lo, hi]。
lo:在最保守的假設下(* 盡量視為 ) 或空),未配對左括號的最小可能數量。hi:在最樂觀的假設下(* 盡量視為 (),未配對左括號的最大可能數量。遍歷每個字元:
(:lo++,hi++(必定增加一個未配對左括號)。):lo--,hi--(必定消耗一個左括號,或讓計數減少)。*:lo--(把 * 視為 )),hi++(把 * 視為 ()。兩個關鍵約束:
hi < 0:即使最樂觀地將所有 * 視為 (,右括號仍過多,字串必定無效,回傳 false。lo = max(lo, 0):未配對左括號不可能為負數,若 lo 降到 0 以下就夾住為 0(即使保守地把 * 視為 ) 也不強迫產生負數)。最終判斷:若 lo == 0,表示存在一種 * 的解釋方式使所有括號完整配對,回傳 true。
時間複雜度: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] 的更新規則?