[LeetCode] 921. Minimum Add to Make Parentheses Valid

A parentheses string is valid if and only if:

• It is the empty string,
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = “()))”, you can insert an opening parenthesis to be “(()))” or a closing parenthesis to be “())))”.

Return the minimum number of moves required to make s valid.

Example 1:
Input: s = “())”
Output: 1

Example 2:
Input: s = “(((“
Output: 3

Constraints:
1 <= s.length <= 1000
s[i] is either ‘(‘ or ‘)’.

使括号有效的最少添加。

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

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

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

括号匹配类型的题目，思路不是栈就是动态规划。这道题只涉及栈。

• 遇到左括号，无条件入栈
• 遇到右括号，如果栈顶有元素且为左括号，则抵消左括号
• 如果栈顶没有元素，无条件入栈

最后看一下栈内元素个数，这些元素就是匹配不上的括号数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minAddToMakeValid(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return 0;
        }

        // normal case
        Deque<Character> stack = new ArrayDeque<>();
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.offerLast(c);
            } else if (c == ')') {
                if (!stack.isEmpty() && stack.peekLast() == '(') {
                    stack.pollLast();
                } else {
                    stack.offerLast(c);
                }
            }
        }
        return stack.size();
    }
}

相关题目

20. Valid Parentheses
678. Valid Parenthesis String
921. Minimum Add to Make Parentheses Valid
1111. Maximum Nesting Depth of Two Valid Parentheses Strings
1003. Check If Word Is Valid After Substitutions
1249. Minimum Remove to Make Valid Parentheses
1541. Minimum Insertions to Balance a Parentheses String
1963. Minimum Number of Swaps to Make the String Balanced
2116. Check if a Parentheses String Can Be Valid