65-使括号有效的最少添加

自己的做法

算法思想

这都不像是中等难度的题目。Easy~

使用栈，遍历当前字符串，如果当前字符是)且栈顶元素为(，就弹出栈，否则就入栈。

遍历结束后，栈中的元素就是需要添加的最少括号数。

算法实现

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> stack;
        
        for(char ch : s) {
            if(ch == ')' && !stack.empty() && stack.top() == '(') {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.size();
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

参考做法

算法思想

平衡法。

要使括号有效，就要保证左括号和右括号同样多。即保证左右括号数量的平衡。

计算(出现的次数减去)出现的次数，如果为0，则表示平衡，括号有效，如果小于0，那么就需要在前面补上(。

所以可以计算给定字符串s的每个前缀子数组的平衡度，如果该子数组平衡度值为负数，说明前面得加上个(；但如果是个正数，说明该子数组的(多于)，那就无法判定，可能后面还有对应的)。

所以可以设定两个变量ans和bal，ans表示需要添加的(的个数，bal表示)需要添加的个数。

遍历字符串，当字符为(，bal加1，否则bal减1。如果bal等于-1，说明从头字符到当前字符的子数组需要添加一个(，那么ans就加1，同时将bal置0，重新开始计数。

最后ans + bal即为答案。

举个例子：例如A = “())”，B = “(()”，A字符串缺(，B字符串缺)。那么当给定字符串为AB时，当遍历到A字符串最后一个字符，即)时，bal为-1，那么ans加1，bal置为0。说明该子字符串需要添加一个(。这时候继续向后遍历，bal代表的就是B的首字符到当前字符的子字符串的平衡度，而不是从整个字符串的首字符开始了。当遍历到B字符串末尾，bal为1，说明需要在后面添加一个)。

所以最后，ans = 1， bal = 1。总共需要添加 ans + bal = 2 个括号。

所以，只有当bal为-1时，ans才加1。即确定没法补救了，必须得添加一个(才会有效。而bal大于0时，因为不知道后面会不会遇到)，所以无法判断，只能继续向后遍历。

算法实现

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0, bal = 0;
        for(char ch : s) {
            bal += ch == '(' ? 1 : -1;
            if(bal == -1) {
                ans++;
                //写成bal = 0 可以更好表达算法思想
                bal++;
            }
        }
        return ans + bal;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。