『LeetCode』921 使括号有效的最少添加

题目

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

【使括号有效的最少添加】简单括号匹配

模拟

提到括号匹配大概立刻就会联想到栈，将左括号入栈，遇到右括号就弹出一个左括号，如果栈空那就不是合理的括号对，如果遍历完栈还有多余的左括号也是不合理的。

这里需要将题目给的序列补充成合理的，那么就在栈空的时候在最左边添一个左括号即可，最后遍历完给栈内没有对应右括号的左括号补充对应数量的右括号即可。

实际上也不需要维护显式的栈，因为栈内全部都是左括号，我们用一个变量记录栈内左括号的数量即可。

# Code language: Python
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        cnt, ans = 0, 0
        for c in s:
            if c == '(': cnt += 1
            else:
                cnt -= 1
                if cnt < 0:
                    ans, cnt = ans + 1, 0
        return ans + cnt

// Code language: Java
class Solution {
    public int minAddToMakeValid(String s) {
        int cnt = 0, ans = 0;
        for (int i = 0, n = s.length(); i < n; ++i) {
            if (s.charAt(i) == '(') ++cnt;
            else {
                if (--cnt < 0) {
                    ++ans; ++cnt;
                }
            }
        }
        return cnt + ans;
    }
}

// Code language: C++
class Solution {
public:
    int minAddToMakeValid(string s) {
        int cnt = 0, ans = 0;
        for (char c: s) {
            if (c == '(') ++cnt;
            else {
                if (--cnt < 0) {
                    ++ans; ++cnt;
                }
            }
        }
        return cnt + ans;
    }
};

/* Code language: JavaScript */
/**
 * @param {string} s
 * @return {number}
 */
var minAddToMakeValid = function(s) {
    let cnt = 0, ans = 0;
    for (let c of s) {
        if (c == '(') ++cnt;
        else {
            if (--cnt < 0) {
                ++ans; ++cnt;
            }
        }
    }
    return cnt + ans;
};

/* Code language: Go */
func minAddToMakeValid(s string) int {
    cnt, ans := 0, 0
    for _, c := range s {
        if c == '(' {
            cnt++
        } else {
            cnt--
            if cnt < 0 {
                ans++; cnt = 0;
            }
        }
    }
    return cnt + ans
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』921 使括号有效的最少添加

题目

标签

题解

模拟