【力扣 leetcode】921：使括号有效的最少添加

￡神魔★判官ぃ 2023-10-09 14:52 12阅读 0赞

## 每日进步 ##

*  **求字符串的子串：** `str.substring(int beginindex, int endindex)`

## 题目 ##

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

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

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

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

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

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid  
> 著作权归领扣网络所有。仅供个人学习，非商用。

## 题解 ##

**方法一：** 贪心算法

*  遍历字符串的每一个字符
    
     *  若字符为`(`，则左括号数量加1。
     *  若字符为`)`，且目前左括号数量不为0，那么就意味着有做括号可以和右括号相匹配。因此，将左括号数减1。
     *  若字符为`)`，且目前左括号数量为0。此时，无左括号可以与右括号匹配，需要添加左括号。故操作次数加1。
 *  此外，如果遍历完后左括号数量`left_num`不为0，那么就意味着有剩余的左括号，需要添加相同数量的右括号与之相匹配。故，操作次数加`left_num`。

class Solution {
        
        public int minAddToMakeValid(String s) {
        
            int left_num = 0, ans = 0;
            char[] arr = s.toCharArray();
    
            for (char x : arr){
        
                if (x == '(')
                    left_num += 1;
                else if (left_num != 0)
                    left_num -= 1;
                else
                    ans += 1;
            }
    
            return left_num + ans;
        }
    }

运行结果如下图所示：  
![结果][5d74010fcffc4ef9922c0bd75c758a71.png_pic_center]

**方法二：** 递归算法  
此方法与快速排序的算法类似，将字符串不断分成子串，计算将每一个子串变为有效括号所需的操作次数，最后求和。  
此方法需要**注意**：最开始的时候，需要将确定能匹配的子串去掉。因为在划分成不同子串之后，无法将不同子串内的括号进行匹配，因此需要先将这些子串排除。

class Solution {
        
        int ans = 0;
    
        public int minAddToMakeValid(String s) {
        
            while(s.contains("()")){
        
                s = s.substring(0, s.indexOf("()")) + s.substring(s.indexOf("()")+2, s.length());
            }
    
            partition(s, 0, s.length());
            return ans;
        }
    
        public void partition(String s, int beginindex, int endindex){
        
            String spart = s.substring(beginindex, endindex);
    
            if (spart.contains(")(")){
        
                partition(spart, 0, spart.indexOf(")(")+1);
                partition(spart, spart.indexOf(")(")+1, spart.length());
                return;
            }
    
            char[] arr = spart.toCharArray();
            int anspart = 0;
    
            for (char x : arr){
        
                if (x == '(')
                    anspart += 1;
                else
                    anspart -= 1;
            }
    
            ans += Math.abs(anspart);
        }
    }

[5d74010fcffc4ef9922c0bd75c758a71.png_pic_center]: https://img-blog.csdnimg.cn/5d74010fcffc4ef9922c0bd75c758a71.png#pic_center