921. 使括号有效的最少添加
921. 使括号有效的最少添加
题目
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
is a valid string.
You are given a parentheses string s
. In one move, you can insert a parenthesis at any position of the string.
- For example, if
s = "()))"
, you can insert an opening parenthesis to be"(**(**)))"
or a closing parenthesis to be"())**)**)"
.
Return the minimum number of moves required to makes
valid.
Example 1:
Input: s =
"())"
Output: 1
Example 2:
Input: s =
"((("
Output: 3
Constraints:
1 <= s.length <= 1000
s[i]
is either'('
or')'
.
题目大意
只有满足下面几点之一,括号字符串才是有效的:
- 它是一个空字符串,或者
- 它可以被写成
AB
(A
与B
连接), 其中A
和B
都是有效字符串,或者 - 它可以被写作
(A)
,其中A
是有效字符串。
给定一个括号字符串 s
,在每一次操作中,你都可以在字符串的任何位置插入一个括号
- 例如,如果
s = "()))"
,你可以插入一个开始括号为"(()))"
或结束括号为"())))"
。
返回 为使结果字符串s
有效而必须添加的最少括号数。
示例 1:
输入: s =
"())"
输出: 1
示例 2:
输入: s =
"((("
输出: 3
提示:
1 <= s.length <= 1000
s
只包含'('
和')'
字符。
解题思路
初始化两个变量:
needLeft
:未匹配的左括号数,初始值为 0。needRight
:需要的右括号数,初始值为 0。
遍历字符串:
- 对于每个字符:
- 如果是左括号
'('
,将needLeft
变量加 1。 - 如果是右括号
')'
:- 如果存在未匹配的左括号(即
needLeft > 0
),则减少needLeft
,因为找到了一个右括号可以与之匹配。 - 否则,增加
needRight
,因为这是一个未匹配的右括号。
- 如果存在未匹配的左括号(即
- 如果是左括号
- 对于每个字符:
最终结果:
- 遍历完成后,剩余的
needLeft
表示未匹配的左括号,needRight
表示未匹配的右括号。两者之和就是需要添加的括号数量。
- 遍历完成后,剩余的
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串s
的长度。我们只需要遍历字符串一次。 - 空间复杂度:
O(1)
,因为我们只使用了两个计数器变量needLeft
和needRight
。
代码
/**
* @param {string} s
* @return {number}
*/
var minAddToMakeValid = function (s) {
let needLeft = 0, // 记录左括号的需求量
needRight = 0; // 记录右括号的需求量
for (let char of s) {
if (char == '(') {
// 对右括号的需求 + 1
needRight++;
} else {
if (needRight > 0) {
// 对右括号的需求 - 1
needRight--;
} else {
// 需插入一个左括号
needLeft++;
}
}
}
return needLeft + needRight;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
1963 | 使字符串平衡的最小交换次数 | [✓] | 栈 贪心 双指针 1+ |