LeetCode 解題筆記：1541. Minimum Insertions to Balance a Parentheses String

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


LeetCode 題目連結：1541. Minimum Insertions to Balance a Parentheses String

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，可以在任意位置、加入任意數量的 $(, )$，最少加入幾個 $(, )$ 可以使 $s$ 變成合法的括號字串。題目底下的提示是用堆疊記錄 $($ 的數量，但其實只要用一個變數 $left$ 記錄數量即可，不需要用堆疊。假設 $s$ 的長度為 $n$，用一個 while 迴圈從索引值 $i = 0$ 開始讀取 $s$ 的字元。如果遇到 $s[i]$ 是左括號，$left + 1$；如果 $s[i]$ 是右括號，再分成以下 2 種狀況：

1. $left == 0$，沒有左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號，補 1 個左括號，答案 $ans + 1$，索引值 $i+1$；如果條件不成立，需要補 1 個左括號、1 個右括號，答案 $ans + 2$。
2. $left > 0$，有 1 個以上的左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號，不需要補括號，索引值 $i+1$，用掉 1 個左括號 $left - 1$；如果條件不成立，用掉 1 個左括號 $left - 1$，需要補 1 個右括號，答案 $ans + 1$。

最後如果 $left > 0$，每 1 個左括號需要補 2 個右括號，答案為 $ans + left * 2$。

Python 程式碼

Runtime: 71 ms, beats 57.89%. Memory: 19.99 MB, beats 37.54%.

class Solution:
    def minInsertions(self, s: str) -> int:
        # 左括號數量，答案，長度，索引值
        left, ans, n, i = 0, 0, len(s), 0
        
        while i < n:
            if s[i] == '(':  # 左括號，left 加 1
                left += 1
                i += 1  # 索引值加 1
            else:  # 右括號
                if left == 0:  # 如果沒有左括號可以配對
                    # 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if i < n-1 and s[i+1] == ')':
                        i += 1  # 索引值加 1
                        ans += 1  # 補 1 個左括號
                    else:  # i+1 出界或 s[i+1] 是左括號
                        ans += 2  # 補 1 個左括號、1 個右括號
                else:  # 如果有 1 個以上的左括號可以配對
                    # 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if i < n-1 and s[i+1] == ')':
                        i += 1  # 索引值加 1
                        left -= 1  # 用掉 1 個左括號
                    else:  # i+1 出界或 s[i+1] 是左括號
                        left -= 1  # 用掉 1 個左括號
                        ans += 1  # 補 1 個右括號
                i += 1  # 索引值加 1
        
        return ans + left * 2  # 剩下的左括號各需要補 2 個右括號

C++ 程式碼

Runtime: 3 ms, beats 81.68%. Memory: 15.64 MB, beats 53.60%.

class Solution {
public:
    int minInsertions(string s) {
        // 左括號數量，答案，長度，索引值
        int left = 0, ans = 0, n = s.size(), i = 0;
        
        while(i < n) {
            if (s[i] == '(') {  // 左括號，left 加 1
                left++;
                i++;  // 索引值加 1
            } else {  // 右括號
                if (left == 0) {  // 如果沒有左括號可以配對
                    // 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if (i < n-1 && s[i+1] == ')') {
                        i++;  // 索引值加 1
                        ans++;  // 補 1 個左括號
                    } else {  // i+1 出界或 s[i+1] 是左括號
                        ans += 2;  // 補 1 個左括號、1 個右括號
                    }
                } else {  // 如果有 1 個以上的左括號可以配對
                    // 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if (i < n-1 && s[i+1] == ')') {
                        i++;  // 索引值加 1
                        left--;  // 用掉 1 個左括號
                    } else {  // i+1 出界或 s[i+1] 是左括號
                        left--;  // 用掉 1 個左括號
                        ans++;  // 補 1 個右括號
                    }
                }
                i++;  // 索引值加 1
            }
        }

        return ans + left * 2;  // 剩下的左括號各需要補 2 個右括號
    }
};

C 語言程式碼

Runtime: 3 ms, beats 62.50%. Memory: 10.33 MB, beats 100.00%.

int minInsertions(char* s) {
    int left = 0, ans = 0, n = strlen(s), i = 0;
        
    while(i < n) {
        if (s[i] == '(') {  // 左括號，left 加 1
            left++;
            i++;  // 索引值加 1
        } else {  // 右括號
            if (left == 0) {  // 如果沒有左括號可以配對
                // 如果 i+1 沒有出界且 s[i+1] 是右括號
                if (i < n-1 && s[i+1] == ')') {
                    i++;  // 索引值加 1
                    ans++;  // 補 1 個左括號
                } else {  // i+1 出界或 s[i+1] 是左括號
                    ans += 2;  // 補 1 個左括號、1 個右括號
                }
            } else {  // 如果有 1 個以上的左括號可以配對
                // 如果 i+1 沒有出界且 s[i+1] 是右括號
                if (i < n-1 && s[i+1] == ')') {
                    i++;  // 索引值加 1
                    left--;  // 用掉 1 個左括號
                } else {  // i+1 出界或 s[i+1] 是左括號
                    left--;  // 用掉 1 個左括號
                    ans++;  // 補 1 個右括號
                }
            }
            i++;  // 索引值加 1
        }
    }

    return ans + left * 2;  // 剩下的左括號各需要補 2 個右括號
}