跳至主要內容

921. 使括号有效的最少添加


921. 使括号有效的最少添加

🟠   🔖  贪心 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

A parentheses string is valid if and only if:

  • It is the empty string,
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A 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 ')'.

题目大意

只有满足下面几点之一,括号字符串才是有效的:

  • 它是一个空字符串,或者
  • 它可以被写成 ABAB 连接), 其中 AB 都是有效字符串,或者
  • 它可以被写作 (A),其中 A 是有效字符串。

给定一个括号字符串 s ,在每一次操作中,你都可以在字符串的任何位置插入一个括号

  • 例如,如果 s = "()))" ,你可以插入一个开始括号为 "(()))" 或结束括号为 "())))"

返回 为使结果字符串s 有效而必须添加的最少括号数

示例 1:

输入: s = "())"

输出: 1

示例 2:

输入: s = "((("

输出: 3

提示:

  • 1 <= s.length <= 1000
  • s 只包含 '('')' 字符。

解题思路

  1. 初始化两个变量

    • needLeft:未匹配的左括号数,初始值为 0。
    • needRight:需要的右括号数,初始值为 0。
  2. 遍历字符串

    • 对于每个字符:
      • 如果是左括号 '(',将 needLeft 变量加 1。
      • 如果是右括号 ')'
        • 如果存在未匹配的左括号(即 needLeft > 0),则减少 needLeft,因为找到了一个右括号可以与之匹配。
        • 否则,增加 needRight,因为这是一个未匹配的右括号。
  3. 最终结果

    • 遍历完成后,剩余的 needLeft 表示未匹配的左括号,needRight 表示未匹配的右括号。两者之和就是需要添加的括号数量。

复杂度分析

  • 时间复杂度: O(n),其中 n 是字符串 s 的长度。我们只需要遍历字符串一次。
  • 空间复杂度: O(1),因为我们只使用了两个计数器变量 needLeftneedRight

代码

/**
 * @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+🟠🀄️open in new window 🔗open in new window