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

题目描述

思路及解法

1.定义int变量res、need分别记录需要插入的左括号数和所需与左括号配对的右括号数；

2.遍历字符串：

2.1.若当为左括号，则need++，表示需要一个右括号与当前左括号配对；
2.2.若当前为右括号，则need–，表示已经有一个右括号与左括号配对；

2.2.1.若发现当前need == -1则表示需要插入一个左括号即res++

3.返回最后需要插入的左括号数和需要和当前左括号配对的右括号数即res + need

复杂度

时间复杂度:

$O(n)$;其中$n$为给定字符串的长度

空间复杂度:

$O(1)$

Code

class Solution {
    /**
     * Minimum Add to Make Parentheses Valid
     *
     * @param s Given string
     * @return int
     */
    public int minAddToMakeValid(String s) {
        // Record the number of left bracket insertion requirements
        int res = 0;
        int need = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                // Add one to the required number of right parentheses
                need++;
            }
            if (s.charAt(i) == ')') {
                // Add one to the required number of left parentheses
                need--;
                if (need == -1) {
                    need = 0;
                    //Subtract one to the required number of right parentheses
                    res++;
                }
            }
        }
        return need + res;
    }
}