使括号有效的最少添加 图解题解

把括号补成合法，最少补几个

给一个只含 ( 和 ) 的字符串 s，你可以在任意位置插入一个 ( 或 )，问最少插入几次能让它变成有效括号串。有效即每个 ( 右边都配得上一个 )、每个 ) 左边都配得上一个 (。题面例子 s=「()))((」，答案是 4。

先数左右括号的个数差，够不够

既然只是补括号，先数出 ( 和 ) 各有几个、看差多少，好像就够了。可 s=「()))((」里两种各 3 个、个数差是 0，实际却要补 4 个。只数个数把顺序丢了：字符串 )( 里两种也各 1 个，但 ) 在前、( 在后谁也配不上谁，得给前面的 ) 补 (、给后面的 ( 补 )，仍要补 2 个。补几个跟总数无关，看的是括号出现的先后。

一遍扫描：( 攒着、) 先配对再记账

换成从左往右扫一遍，手里拿两个计数器：open 记当前攒着、还没配对的 ( 有几个，need 记遇到过、注定配不上的孤儿 ) 有几个。扫到 ( 就 open 加 1，攒着等右边的 ) 来配；扫到 )，open 大于 0 就抵消一个 (、open 减 1，这对括号自己就合法了，open 已经是 0 就没得配、这个 ) 是孤儿，need 加 1。

扫完后，need 是补不上的孤儿 )，open 是余下没人配的 (。这两笔为什么不能相互抵掉？孤儿 ) 一定落在余下的 ( 左边——若某个 ( 在它左边，扫到那个 ) 时还有 ( 可配，它压根不会变孤儿。左边缺的补左边、右边多的补右边，隔着位置合并不了，所以是相加不是相减。

落地成代码，配对和收尾都拿捏住

代码就是一个 for 循环扫字符串：遇到 ( 就 open 加 1；遇到 ) 先看 open，大于 0 就 open 减 1、否则 need 加 1；结束返回 need 加 open。遇到 ) 得先尝试配对再记账——直接 need 加 1、跳过配对，合法的对子也被算成缺口，答案就偏大。结尾余下的每个 ( 各缺一个 )，只返回 need、漏掉 open 就会少算。

拿「()))((」一格一格算到 4

从头走 s=「()))((」：第 0 位 (，open 变 1。第 1 位 )，open 大于 0，抵消一对，open 减回 0。第 2 位又是 )，open 是 0 没得配，need 变 1。第 3 位还是 )，open 仍 0，need 变 2。第 4 位 (，open 变 1。第 5 位又 (，open 变 2。扫完 need=2、open=2，相加得 4，正是要补的括号数。

再拿 (() 验漏加 open 的坑：两个 ( 让 open 攒到 2，第 2 位 ) 抵消一对、open 减到 1，全程没孤儿、need 一直 0。扫完 need=0、open=1，答案 1——若只返回 need 就成 0，可这个 ( 还缺一个 )。

为什么扫一遍就够快

从左到右只扫一遍字符串，每个字符看一次、做的是加减法，时间 O(n)，n 是字符串长度。额外空间只有 open、need 两个整数计数器，不随字符串变长而增多，空间 O(1)。一趟遍历就把要补的括号全数清了。

Python

class Solution:
    def minAddToMakeValid(self, s):
        open_ = 0   # 没配对的 ( 数
        need = 0    # 必须补 ( 的孤儿 ) 数
        for c in s:
            if c == '(':
                open_ += 1
            elif open_ > 0:        # ) 且手里有 ( 可配
                open_ -= 1
            else:                  # ) 但没 ( 可配
                need += 1
        return need + open_

C++

class Solution {
public:
    int minAddToMakeValid(string s) {
        int open = 0, need = 0;
        for (char c : s) {
            if (c == '(') {
                open++;
            } else if (open > 0) {   // ) 且有 ( 可配
                open--;
            } else {                 // ) 无 ( 可配
                need++;
            }
        }
        return need + open;
    }
};

Java

class Solution {
    public int minAddToMakeValid(String s) {
        int open = 0, need = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                open++;
            } else if (open > 0) {   // ) 且有 ( 可配
                open--;
            } else {                 // ) 无 ( 可配
                need++;
            }
        }
        return need + open;
    }
}