LeetCode 解題筆記：921. Minimum Add to Make Parentheses Valid

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


LeetCode 題目連結：921. Minimum Add to Make Parentheses Valid

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，可以在 $s$ 之中任何位置加入任意數量的左、右括號，如果要將 $s$ 變成合法的括號字串，最少要加入幾個括號？

這題可以仿照判斷括號是否成對的寫法，用一個堆疊 $st$ 儲存待配對的左括號。用一個 for 迴圈依序讀取 $c = s[i]$，如果 $c$ 是 $($，$st$ 推入 $($；如果 $c$ 是 $)$，假設 $st$ 之中有可以配對的 $($，移除 $st[-1]$，反之需要加上一個 $($，答案 $ans$ 加 1。最後回傳的答案要再加上 $st$ 之中待配對的 $($ 數量，各需要加上一個 $)$ 配對。

依照上面的想法，其實我們只需要記錄待配對的左括號數量，可以不需要堆疊，用一個變數 $balance$ 記錄 $($ 數量 - $)$ 數量。用一個 for 迴圈依序讀取 $c = s[i]$，如果 $c$ 是 $($，$balance$ 加 1；如果 $c$ 是 $)$，假設 $balance > 0$，有可以配對的 $($，$balance$ 減 1，反之需要加上一個 $($，答案 $ans$ 加 1。最後回傳的答案要再加上 $balance$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 18.97 MB, beats 99.91%.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        st = []  # 待配對的左括號
        for c in s:
            if c == '(':  # 如果 c 是左括號，推入 st
                st.append('(')
            else:  # 如果 c 是右括號
                if st: st.pop()  # 有可以配對的左括號，移除 st 最後一項
                else: ans += 1  # 沒有可以配對的左括號，ans 加 1
        # ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + len(st)

Runtime: 0 ms, beats 100.00%. Memory: 19.08 MB, beats 98.46%.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        balance = 0  # 左括號數量 - 右括號數量
        for c in s:
            if c == '(':  # 如果 c 是左括號，balance 加 1
                balance += 1
            else:  # 如果 c 是右括號
                if balance > 0: balance -= 1  # 有可以配對的左括號，balance 減 1
                else: ans += 1  # 沒有可以配對的左括號，ans 加 1
        # ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + balance

C++ 程式碼

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

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0;  // 答案
        stack<char> st;  // 待配對的左括號
        for(char c : s) {
            if (c == '(') {  // 如果 c 是左括號，推入 st
                st.push('(');
            } else {  // 如果 c 是右括號
                if (!st.empty()) st.pop();  // 有可以配對的左括號，移除 st 最後一項
                else ans++;  // 沒有可以配對的左括號，ans 加 1
            }
        }
        // ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + (int)st.size();
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 8.25 MB, beats 96.26%.

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0, balance = 0;  // 答案，左括號數量 - 右括號數量
        for(char c : s) {
            if (c == '(') {  // 如果 c 是左括號，balance 加 1
                balance++;
            } else {  // 如果 c 是右括號
                if (balance > 0) balance--;  // 有可以配對的左括號，balance 減 1
                else ans++;  // 沒有可以配對的左括號，ans 加 1
            }
        }
        // ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + balance;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.64 MB, beats 54.41%.

int minAddToMakeValid(char* s) {
    // 長度，答案，左括號數量 - 右括號數量
    int n = strlen(s), ans = 0, balance = 0;
    for(int i = 0; i < n; i++) {
        if (s[i] == '(') {  // 如果 s[i] 是左括號，balance 加 1
            balance++;
        } else {  // 如果 s[i] 是右括號
            if (balance > 0) balance--;  // 有可以配對的左括號，balance 減 1
            else ans++;  // 沒有可以配對的左括號，ans 加 1
        }
    }
    // ans 還要加上剩下的左括號數量，各需要一個右括號配對
    return ans + balance;
}