給定一個只包含
(、)和*的字串，其中*可以視為(、)或空字串。判斷該字串是否為合法的括號字串。
Example:
Input: s = ”())” Output: true ( 視為 ’(‘)
Intuition
TIP
維護左括號數量的可能範圍 [low, high]：* 讓範圍擴展，若 high 變負則不可能，最後 low 需為 0。
low：未匹配的左括號最少可能有幾個（*盡量當)或空字串）high：未匹配的左括號最多可能有幾個（*盡量當(）- 遇到
(：low++, high++ - 遇到
)：low—, high— - 遇到
*：low—, high++ - 若
high < 0：右括號太多，不可能合法 low = max(low, 0)：low 不能為負（不需要多餘的右括號）
Approaches
1. DP — O(n^2) / O(n^2)
- Idea:
dp[i][j]代表前 i 個字元是否能使未匹配的左括號數恰好為 j。 - Time:
O(n^2) - Space:
O(n^2)或用空間優化到O(n)
class Solution {
fun checkValidString(s: String): Boolean {
val n = s.length
val dp = Array(n + 1) { BooleanArray(n + 1) }
dp[0][0] = true
for (i in 1..n) {
for (j in 0..n) {
when (s[i - 1]) {
'(' -> dp[i][j] = j > 0 && dp[i - 1][j - 1]
')' -> dp[i][j] = dp[i - 1][j + 1]
'*' -> {
dp[i][j] = dp[i - 1][j] // * as empty
if (j > 0) dp[i][j] = dp[i][j] || dp[i - 1][j - 1] // * as (
dp[i][j] = dp[i][j] || dp[i - 1][j + 1] // * as )
}
}
}
}
return dp[n][0]
}
}⭐ 2. Greedy (range tracking) — O(n) / O(1)
- Idea: 用
low和high追蹤未匹配左括號數量的可能範圍，一次遍歷即可。 - Time:
O(n) - Space:
O(1)
class Solution {
fun checkValidString(s: String): Boolean {
var low = 0
var high = 0
for (c in s) {
when (c) {
'(' -> { low++; high++ }
')' -> { low--; high-- }
'*' -> { low--; high++ }
}
if (high < 0) return false
low = maxOf(low, 0)
}
return low == 0
}
}🔑 Takeaways
- Pattern: 範圍追蹤 Greedy — 用 [min, max] 區間涵蓋所有可能狀態
- Key trick: 當有多種選擇時，不需要枚舉每種選擇，只需追蹤可能的範圍；
low = max(low, 0)是防止「虛擬右括號」的關鍵