678. Valid Parenthesis String

Medium

Description

給定一個只包含 (、) 和 * 的字串，其中 * 可以視為 (、) 或空字串。判斷該字串是否為合法的括號字串。

Example:

Input: s = “())” Output: true ( 視為 ‘(’)

Intuition#

維護左括號數量的可能範圍 [low, high]：* 讓範圍擴展，若 high 變負則不可能，最後 low 需為 0。

low：未匹配的左括號最少可能有幾個（* 盡量當 ) 或空字串）
high：未匹配的左括號最多可能有幾個（* 盡量當 (）
遇到 (：low++, high++
遇到 )：low–, high–
遇到 *：low–, high++
若 high < 0：右括號太多，不可能合法
low = max(low, 0)：low 不能為負（不需要多餘的右括號）

Approaches#

1: DP#

概念: dp[i][j] 代表前 i 個字元是否能使未匹配的左括號數恰好為 j。
時間複雜度: O(n^2)
空間複雜度: 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（範圍追蹤）#

概念: 用 low 和 high 追蹤未匹配左括號數量的可能範圍，一次遍歷即可。
時間複雜度: O(n)
空間複雜度: 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] 區間涵蓋所有可能狀態
關鍵技巧: 當有多種選擇時，不需要枚舉每種選擇，只需追蹤可能的範圍；low = max(low, 0) 是防止「虛擬右括號」的關鍵