给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
- 任何左括号
'(' 必须对应两个连续的右括号 '))' 。
- 左括号
'(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和
"(()))" 都是不平衡的。
你可以在任意位置插入字符 ‘(‘ 和 ‘)’ 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
**输入：** s = "(()))"
**输出：** 1
**解释：** 第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：
**输入：** s = "())"
**输出：** 0
**解释：** 字符串已经平衡了。
示例 3：
**输入：** s = "))())("
**输出：** 3
**解释：** 添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：
**输入：** s = "(((((("
**输出：** 12
**解释：** 添加 12 个 ')' 得到平衡字符串。
示例 5：
**输入：** s = ")))))))"
**输出：** 5
**解释：** 在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5s 只包含 '(' 和 ')' 。
方法一：贪心
这道题是括号匹配的题目。每个左括号必须对应两个连续的右括号，而且左括号必须在对应的连续两个右括号之前。
对于括号匹配的题目，常用的做法是使用栈进行匹配，栈具有后进先出的特点，因此可以保证右括号和最近的左括号进行匹配。其实，这道题可以使用计数代替栈，进行匹配时每次都取距离当前位置最近的括号，就可以确保平衡。
由于每个左括号要匹配两个连续的右括号，显然维护左括号的个数更为方便。从左到右遍历字符串，在遍历过程中维护左括号的个数以及插入次数。
如果遇到左括号，则将左括号的个数加 1，并将下标加 1。
如果遇到右括号，则需要进行两步操作，一是和前面的左括号进行匹配，二是需要确保有两个连续的右括号。具体做法如下：
和前面的左括号进行匹配，如果左括号的个数大于 0，则说明前面有左括号可以匹配，因此将左括号的个数减 1，否则说明前面没有左括号可以匹配，需要插入一个左括号才能匹配，因此将插入次数加 1；
确保有两个连续的右括号，如果当前下标的后面的一个字符是右括号，则当前下标和后一个下标是两个连续的右括号，因此将下标加 2，否则就需要在当前位置的后面插入一个右括号，才有两个连续的右括号，因此将插入次数加 1，并将下标加 1。
遍历结束后，需要检查左括号的个数是否为 0。如果不为 0，则说明还有剩下的左括号没有匹配，对于每个剩下的左括号，需要插入两个右括号才能匹配，此时需要插入的右括号个数为剩下的左括号个数乘以 2，将需要插入的右括号个数加到插入次数。
无论是哪种插入的情况，都是在遇到括号无法进行匹配的情况下才进行插入，因此上述做法得到的插入次数是最少的。
[sol1-Java]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
26
27
28
29
| class Solution {
public int minInsertions(String s) {
int insertions = 0;
int leftCount = 0;
int length = s.length();
int index = 0;
while (index < length) {
char c = s.charAt(index);
if (c == '(') {
leftCount++;
index++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
insertions++;
}
if (index < length - 1 && s.charAt(index + 1) == ')') {
index += 2;
} else {
insertions++;
index++;
}
}
}
insertions += leftCount * 2;
return insertions;
}
}
|
[sol1-C#]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
26
27
28
29
| public class Solution {
public int MinInsertions(string s) {
int insertions = 0;
int leftCount = 0;
int length = s.Length;
int index = 0;
while (index < length) {
char c = s[index];
if (c == '(') {
leftCount++;
index++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
insertions++;
}
if (index < length - 1 && s[index + 1] == ')') {
index += 2;
} else {
insertions++;
index++;
}
}
}
insertions += leftCount * 2;
return insertions;
}
}
|
[sol1-C++]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
26
27
28
29
30
| class Solution {
public:
int minInsertions(string s) {
int insertions = 0;
int leftCount = 0;
int length = s.size();
int index = 0;
while (index < length) {
char c = s[index];
if (c == '(') {
leftCount++;
index++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
insertions++;
}
if (index < length - 1 && s[index + 1] == ')') {
index += 2;
} else {
insertions++;
index++;
}
}
}
insertions += leftCount * 2;
return insertions;
}
};
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def minInsertions(self, s: str) -> int:
length = len(s)
insertions = leftCount = index = 0
while index < length:
if s[index] == "(":
leftCount += 1
index += 1
else:
if leftCount > 0:
leftCount -= 1
else:
insertions += 1
if index < length - 1 and s[index + 1] == ")":
index += 2
else:
insertions += 1
index += 1
insertions += leftCount * 2
return insertions
|
复杂度分析
