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

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

力扣题目链接：https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/

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

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

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

方法一：栈

用栈的思想：如果遇到左括号就入栈，遇到右括号就看栈是否为空。如果栈不空，就出栈一个左括号；否则就将右括号入栈。

最终输出栈中元素的个数，就是未匹配的括号数，也就是“使括号有效的最少添加”

• 时间复杂度$O(n)$，其中$n$是字符串长度
• 空间复杂度$O(n)$

方法二：模拟栈

延续方法一的思想，能否不真正用栈来实现呢？

只需要使用两个变量，left记录栈中有多少个左括号，right记录栈中有多少个右括号。

注意，一旦右括号入栈，就说明前面没有“未匹配的左括号”了，右括号将永远留在栈底无法出栈。

因此，在遍历字符串的过程中，遇到左括号就left++，遇到右括号就看left是否为0。若不为零，就说明栈中有左括号，就left--；否则说明栈中无左括号，就right++

• 时间复杂度$O(n)$，其中$n$是字符串长度
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int minAddToMakeValid(string& s) {
        int left = 0;
        int right = 0;
        for (char& c : s) {
            if (c == '(') {
                left++;
            }
            else {
                if (left) {
                    left--;
                }
                else {
                    right++;
                }
            }
        }
        return right + left;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127158816