LeetCode 解題筆記：678. Valid Parenthesis String

作者：王一哲
日期：2026年10月4日


LeetCode 題目連結：678. Valid Parenthesis String

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, *, )$，其中 $*$ 可以當作 $($、$)$ 或空字串，要檢查 $s$ 之中的括號是否成對。這題下方的提示 1 是用遞迴與回溯窮舉將 $*$ 當作 $($、$)$ 或空字串所有可能的組合，但這個寫法的時間複雜度比較高，先不考慮。提示 2 是用動態規畫解題，用 $dp[i][j]$ 代表子字串 $s[i : j+1]$ 是否合法，寫法比較複雜，先不考慮。提示 3 是用堆疊記錄括號，討論區當中看起來最多人採用的是堆疊的寫法，看起來最可行。

我是用兩個堆疊 $left$、$star$，分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$，接下來分成 3 個狀況：

1. $c == '('$，$i$ 推入 $left$。
2. $c == '*'$，$i$ 推入 $star$。
3. $c == ')'$，優先使用 $($ 配對，如果有 $left$ 有資料，移除 $left$ 最後一項。如果沒有 $($ 可以配對，再用 $*$ 配對，如果 $star$ 有資料，移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對，回傳 Fasle。

再用一個 while 迴圈處理剩下的 $($，如果 $left$ 有資料繼續執行。由於可以將 $left[-1]$ 右側的 $*$ 當作 $)$ 配對，如果 $star$ 有資料而且 $left[-1] < star[-1]$，移除 $left[-1]$ 及 $star[-1]$；如果條件不成立，回傳 False。跑完 while 迴圈之後，由於 $*$ 可以當作空字串，$star$ 不需要清空，$s$ 合法，回傳 True。

這題還有一個最極致的寫法，只用兩個整數變數 min_open、max_open，分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，接下來分成 3 個狀況：

1. $c == '('$，min_open 加 1，max_open 加 1。
2. $c == '*'$，$*$ 當作 $)$，min_open 減 1；$*$ 當作 $($，max_open 加 1。
3. $c == ')'$，min_open 減 1，max_open 減 1。

如果遇到 max_open 小於 0，右括號太多，回傳 False。如果 min_open 小於 0，前面將過多的 $*$ 當作 $)$，取部分 $*$ 當作 $($，將 min_open 歸零。跑完 for 迴圈之後，min_open 必須等於零。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 28.53%.

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)  # 長度
        left = []  # 左括號於 s 之中的索引值
        star = []  # 星號於 s 之中的索引值

        for i in range(n):
            c = s[i]
            if c == '(':  # 左括號，i 推入 left
                left.append(i)
            elif c == '*':  # 星號，i 推入 star
                star.append(i)
            else:  # 右括號，優先配對左括號
                if left:  # 有左括號能配對，移除 left 最後一項
                    left.pop()
                elif star:  # 有星號能配對，移除 star 最後一項
                    star.pop()
                else:  # 沒有左括號或星號能配對，回傳 False
                    return False
        
        while left:  # 處理剩下的左括號，取右側的星號配對
            if star and star[-1] > left[-1]:
                left.pop()
                star.pop()
            else:  # 沒有可以配對的星號，回傳 False
                return False
        # 跑完上面的 while 迴圈時 left 已經清空，* 可以是空字串，star 不需要清空
        return True

Runtime: 0 ms, beats 100.00%. Memory: 19.19 MB, beats 89.99%.

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open, max_open = 0, 0  # 未配對左括號可能的最少、最多數量
        
        for c in s:
            if c == '(':  # 左括號
                min_open += 1  # 最少數量加 1
                max_open += 1  # 最多數量加 1
            elif c == ')':  # 右括號
                min_open -= 1  # 最少數量減 1
                max_open -= 1  # 最多數量減 1
            else:  # 星號
                min_open -= 1  # 當作 )，最少數量減 1
                max_open += 1  # 當作 (，最多數量加 1
            
            # 最多數量小於 0，右括號太多，回傳 False
            if max_open < 0: return False
            
            # 最少數量小於 0，前面將過多的 * 當作 )，取部分 * 當作 (，將 min_open 歸零
            if min_open < 0: min_open = 0
        
        # 最後 min_open 必須等於零
        return min_open == 0

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.15 MB, beats 47.91%.

class Solution {
public:
    bool checkValidString(string s) {
        int n = (int)s.size();  // 長度
        stack<int> left, star;  // 左括號於 s 之中的索引值，星號於 s 之中的索引值

        for(int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {  // 左括號，i 推入 left
                left.push(i);
            } else if (c == '*') {  // 星號，i 推入 star
                star.push(i);
            } else {  // 右括號，優先配對左括號
                if (!left.empty()) {  // 有左括號能配對，移除 left 最後一項
                    left.pop();
                } else if (!star.empty()) {  // 有星號能配對，移除 star 最後一項
                    star.pop();
                } else {  // 沒有左括號或星號能配對，回傳 False
                    return false;
                }
            }
        }

        while(!left.empty()) {  // 處理剩下的左括號，取右側的星號配對
            if (!star.empty() && star.top() > left.top()) {
                left.pop();
                star.pop();
            } else {  // 沒有可以配對的星號，回傳 False
                return false;
            }
        }
        
        // 跑完上面的 while 迴圈時 left 已經清空，* 可以是空字串，star 不需要清空
        return true;
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 7.96 MB, beats 93.14%.

class Solution {
public:
    bool checkValidString(string s) {
        int min_open = 0, max_open = 0;  // 未配對左括號可能的最少、最多數量
        for(char c : s) {
            if (c == '(') {  // 左括號
                min_open++;  // 最少數量加 1
                max_open++;  // 最多數量加 1
            } else if (c == ')') {  // 右括號
                min_open--;  // 最少數量減 1
                max_open--;  // 最多數量減 1
            } else {  // 星號
                min_open--;  // 當作 )，最少數量減 1
                max_open++;  // 當作 (，最多數量加 1
            }

            // 最多數量小於 0，右括號太多，回傳 false
            if (max_open < 0) {
                return false;
            }

            // 最少數量小於 0，前面將過多的 * 當作 )，取部分 * 當作 (，將 min_open 歸零
            if (min_open < 0) {
                min_open = 0;
            }
        }
        
        // 最後 min_open 必須等於零
        return min_open == 0;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.61 MB, beats 12.24%.

bool checkValidString(char* s) {
    int n = strlen(s);  // 長度
    int min_open = 0, max_open = 0;  // 未配對左括號可能的最少、最多數量
    for(int i = 0; i < n; i++) {
        char c = s[i];
        if (c == '(') {  // 左括號
            min_open++;  // 最少數量加 1
            max_open++;  // 最多數量加 1
        } else if (c == ')') {  // 右括號
            min_open--;  // 最少數量減 1
            max_open--;  // 最多數量減 1
        } else {  // 星號
            min_open--;  // 當作 )，最少數量減 1
            max_open++;  // 當作 (，最多數量加 1
        }

        // 最多數量小於 0，右括號太多，回傳 false
        if (max_open < 0) {
            return false;
        }

        // 最少數量小於 0，前面將過多的 * 當作 )，取部分 * 當作 (，將 min_open 歸零
        if (min_open < 0) {
            min_open = 0;
        }
    }
    // 最後 min_open 必須等於零
    return min_open == 0;
}