LeetCode_栈_中等_921.使括号有效的最少添加

拼搏现实的明天。 2023-10-07 20:07 32阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。  
例如，如果 s = “()))” ，你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。  
返回为使结果字符串 s 有效而必须添加的最少括号数。

**示例 1：**  
输入：s = “())”  
输出：1

**示例 2：**  
输入：s = “(((”  
输出：3

**提示：**  
1 <= s.length <= 1000  
s 只包含 ‘(’ 和 ‘)’ 字符。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid

## 2.思路 ##

（1）栈  
① 用变量 res 来记录使括号有效的最少添加次数，其初始值为 0，并定义栈 stack；  
② 遍历字符串 s，记当前字符为 c，并做出以下判断：  
1）c 为左括号，则将其入栈；  
2）c 为右括号，如果此时栈不为空，则说明有左括号与其匹配，并将栈顶的左括号出栈，否则需要添加一个左括号，即 res++；  
③ 遍历结束后，如果栈中还有剩余的左括号，则说明还需要添加同等数量的右括号使之有效，所以 res 还需加上 stack.size()；  
④ 返回 res；

> 注意：本题还可以对空间复杂度进行优化，由于本题只需求解必须添加的最少括号数量，所以可以**用变量 leftCnt 来代替 stack**。具体来说，用 leftCnt 的值来反映栈中左括号的数量，如果左括号入栈，则 leftCnt++；如果左括号出栈，则 leftCnt–；这样一来便降低了空间复杂度。

相关题目：  
[LeetCode\_栈\_简单\_20.有效的括号][LeetCode_20.]  
[LeetCode\_递归\_回溯算法\_中等\_22.括号生成][LeetCode_22.]  
[LeetCode\_栈\_动态规划\_困难\_32.最长有效括号][LeetCode_32.]  
[LeetCode\_回溯\_困难\_301. 删除无效的括号][LeetCode_301.]  
[LeetCode\_栈\_中等\_856.括号的分数][LeetCode_856.]

## 3.代码实现（Java） ##

//思路1————栈
    class Solution {
        
        public int minAddToMakeValid(String s) {
        
            int res = 0;
            int length = s.length();
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < length; i++) {
        
                char c = s.charAt(i);
                if (c == '(') {
        
                    stack.push(c);
                } else {
        
                    if (stack.isEmpty()) {
        
                        res++;
                    } else {
        
                        stack.pop();
                    }
                }
            }
            res += stack.size();
            return res;
        }
    }
    
    //用变量 leftCnt 来代替 stack 的写法
    class Solution {
        
        public int minAddToMakeValid(String s) {
        
            int res = 0;
            int length = s.length();
            int leftCnt = 0;
            for (int i = 0; i < length; i++) {
        
                char c = s.charAt(i);
                if (c == '(') {
        
                    leftCnt++;
                } else {
        
                    if (leftCnt == 0) {
        
                        res++;
                    } else {
        
                        leftCnt--;
                    }
                }
            }
            res += leftCnt;
            return res;
        }
    }

[LeetCode_20.]: https://blog.csdn.net/weixin_43004044/article/details/118957884
[LeetCode_22.]: https://blog.csdn.net/weixin_43004044/article/details/123493807
[LeetCode_32.]: https://blog.csdn.net/weixin_43004044/article/details/122975965
[LeetCode_301.]: https://blog.csdn.net/weixin_43004044/article/details/125029726
[LeetCode_856.]: https://blog.csdn.net/weixin_43004044/article/details/127220452