【2022-10-04每日一题】921. 使括号有效的最少添加[Medium]

2022-10-04
1分钟阅读时长

2022-10-04每日一题:921. 使括号有效的最少添加

难度:Medium

标签:栈 、 贪心 、 字符串

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

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

给定一个括号字符串 s ,移动N次,你就可以在字符串的任何位置插入一个括号。

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

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

 

示例 1:

输入:s = "())"
输出:1

示例 2:

输入:s = "((("
输出:3

 

提示:

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

方法一:

详细思路过程见官方题解,这里只做个人刷题记录,方便后续查询阅读

从左到右遍历字符串,在遍历过程中维护左括号的个数以及添加次数。

  • 如果遇到左括号,则将左括号的个数加 1。

  • 如果遇到右括号,则需要和前面的左括号进行匹配,具体做法如下:

    • 如果左括号的个数大于 0,则前面有左括号可以匹配,因此将左括号的个数减 1,表示有一个左括号和当前右括号匹配;

    • 如果左括号的个数等于 0,则前面没有左括号可以匹配,需要添加一个左括号才能匹配,因此将添加次数加 1。

遍历结束后,需要检查左括号的个数是否为 0

func minAddToMakeValid(s string) int {
    left, ans := 0, 0
    for _, ch := range s {
        if ch == '(' {
            left++
        } else if left > 0 {
            left--
        } else {
            ans++
        }
    }
	return left + ans
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串的长度。遍历字符串一次。
  • 空间复杂度:O(1)。只需要维护常量的额外空间。

LeetCode题库地址