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 ')'.

题目大意

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

它是一个空字符串，或者
它可以被写成 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;
};

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

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目