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

LeetCode第921题，难度为中等。这又是一题括号相关的题目。

原题地址：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/

题目描述：

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

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

它是一个空字符串，或者

它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者

它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"

输出：1

示例 2：

输入："((("

输出：3

示例 3：

输入："()"

输出：0

示例 4：

输入："()))(("

输出：4

提示：

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

又是一题和括号是否有效相关的题目。所以就用老朋友栈来做辅助。

每次都将左括号（放入栈中，遇到右括号就将（从栈中取出来。最后还无法配对的左括号（数量就是栈中元素的大小了。

中文官网题解：

https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/solution/

个人题解：

class Solution {
    public int minAddToMakeValid(String S) {
         Stack<Character> stack = new Stack<>();
        for (char c : S.toCharArray()) {
            if (stack.empty()) {
                stack.push(c);
            } else {
                char sc = stack.pop();
                if (!(sc == '(' && c == ')')) {
                    stack.push(sc);
                    stack.push(c);
                }
            }
        }
        return stack.size();
    }
}

结果：

......（贴上自己的代码的运行结果）