Leetcode 1541. Minimum Insertions to Balance a Parentheses String (括号问题好题)

1541. Minimum Insertions to Balance a Parentheses String
      Medium

Given a parentheses string s containing only the characters ‘(’ and ‘)’. A parentheses string is balanced if:

Any left parenthesis ‘(’ must have a corresponding two consecutive right parenthesis ‘))’.
Left parenthesis ‘(’ must go before the corresponding two consecutive right parenthesis ‘))’.
In other words, we treat ‘(’ as an opening parenthesis and ‘))’ as a closing parenthesis.

For example, “())”, “())(())))” and “(())())))” are balanced, “)()”, “()))” and “(()))” are not balanced.
You can insert the characters ‘(’ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = “(()))”
Output: 1
Explanation: The second ‘(’ has two matching ‘))’, but the first ‘(’ has only ‘)’ matching. We need to add one more ‘)’ at the end of the string to be “(())))” which is balanced.
Example 2:

Input: s = “())”
Output: 0
Explanation: The string is already balanced.
Example 3:

Input: s = “))())(”
Output: 3
Explanation: Add ‘(’ to match the first ‘))’, Add ‘))’ to match the last ‘(’.

Constraints:

1 <= s.length <= 105
s consists of ‘(’ and ‘)’ only.

解法1：这题其实不简单。关键是来了左括号时，当前所需右括号数目是奇数的处理。
注意：
当来了’(‘括号时，
a. 如果当前所需右括号数目rightNeeded是偶数，那没什么大关系，再把rightNeeded +2就可以。比如输入"(())"，rightNeeded=2，那再来一个’('，rightNeeded=4。
b. 如果当前所需右括号数目rightNeeded是奇数，那么比较麻烦，我们必须在新来左括号’(‘的时候消掉一个多余的右括号，这样，rightNeeded就是偶数，跟a的情况一样。怎么消掉呢？那我们再增加左括号，消掉一个右括号就可以了。
比如输入"(()"，rightNeeded=3。再来一个’(‘，此时我们必须在这个新来的’(‘前面加上一个’('，即"((()("，这样，leftNeeded++, rightNeeded–，就可以把rightNeeded变成偶数了。
举例：
“(()))(()))()())))”

b. from labuladong 补充一下“当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号”，这个地方如果不做判断，那么 "()()))“ 和 ")()))“这两种情况(能造成 need为奇数的也就这两种情况，一个是need==-1造成的，一个是本来就缺一个右括号)结果都为0，也就是说不加奇偶判断的话，是不能保证按”())“顺序闭合的，一个左括号出现之前，必须要保证之前的左括号都已经匹配完或者一个右括号也没匹配，所以这句话应该"当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号，来匹配之前缺一个右括号的左括号”

class Solution {
public:
    int minInsertions(string s) {
        //int n = s.size();
        int leftMustAdd = 0, rightMustAdd = 0, leftNeed = 0, rightNeed = 0;
        
        for (auto c : s) {
            if (c == '(') {
                rightNeed += 2;
                if (rightNeed & 0x1) { //consider "()()))" and ")()))"
                    //leftMustAdd++;
                    rightMustAdd++;
                    rightNeed--;
                }
            } else { // ')'
                rightNeed--;
                if (rightNeed == -1) {
                    leftMustAdd++;
                    rightNeed = 1;
                }
            }
        }
        return leftMustAdd + rightMustAdd + leftNeed + rightNeed;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

谈谈我的理解：

1. 这题要分清两种情况。情况1是当前的括号分布是不合理的，我们必须现在把它变得合理，也就是现在就主动加一些括号，而不是被动等未来的括号来解决不合理的情况，这也就是leftMustAdd和rightMustAdd使用的情形。情况2是当前的括号分布是不合理的，但是我们现在不必加括号，而是可以被动的等待未来的括号来解决不合理的情况，这也就是leftNeed和rightNeed使用的情形。
   注意：题目上说的"Left parenthesis ‘(’ must go before the corresponding two consecutive right parenthesis ‘))’."，也就是左括号后面必须跟两个连续的右括号！也就是说’()()))’ 这种情况是不合格的，因为第一个左括号后面的两个右括号没有连续。
   举例1：()):
   当遇到第1个字符’(‘时，我们需要2个’)‘，这个我们可以被动等未来的右括号，所以rightNeed+=2。
   当遇到第2个字符’)‘时，因为它已经是右括号，所以rightNeed–。此时rightNeed=1，我们只需要被动等未来的右括号就可以了。
   当遇到第3个字符’)‘时，因为它已经是右括号，所以rightNeed–。此时rightNeed=0。万事大吉。
   所以最后什么字符都不用加。
   举例2：()(
   第1，2个字符同上面的情况。
   当遇到第3个字符’(‘时，因为它是左括号，而且rightNeed=1。注意这里的rightNeed是之前的左括号所需要的，当前的左括号还需要2个’)'。所以rightNeed+=2。而之前的左括号所需的那个rightNeed已经不能指望后面的右括号了，必须在当前的左括号之前就解决，所以我们必须主动在当前左括号前面加上一个右括号。注意这里不能简单的将rightNeed–。因为我们强制加了一个右括号，这个必须算在最后的结果里面。所以rightMustAdd++，这个抵消了一个rightNeed，所以rightNeed–。
2. if (rightNeed & 0x1)这里能不能改成if (rightNeed == 1)呢？不行，因为前面有累计的rightNeed。
   考虑case “()()))”。
   当遇到第1个字符’(‘时，我们需要2个’)‘，这个我们可以被动等未来的右括号，所以rightNeed+=2。
   当遇到第2个字符’)‘时，因为它已经是右括号，所以rightNeed–。此时rightNeed=1，我们只需要被动等未来的右括号就可以了。
   当遇到第3个字符’(‘时，因为它是左括号，所以rightNeed+=2。此时rightNeed=3，而不是1。
   举例3：()))
   当遇到最后一个字符’)‘时，rightNeed=-1。这时候我们不能指望等后面的’(‘或’)‘,必须在这个字符前面就解决这个匹配的问题，因为后面不管括号怎么来都不解决问题。所以leftMustAdd++ (注意写成leftMustAdd=1不对，参考例子")))))))")。这个时候因为新加的左括号需要2个右括号，所以rightNeed要加2，所以rightNeed=1。