leetcode-921-Minimum-Add-to-Make-Parentheses-Valid

发表于   |  

描述

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, or
  • 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.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

1
2
Input: "())"
Output: 1

Example 2:

1
2
Input: "((("
Output: 3

Example 3:

1
2
Input: "()"
Output: 0

Example 4:

1
2
Input: "()))(("
Output: 4

分析

利用栈的特性来模拟左右括号的匹配过程，最后剩下的不能匹配的括号就是需要增加的括号的最小值。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minAddToMakeValid(String S) {
        Stack<Character> stack = new Stack<>();
        for (char c: S.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        return stack.size();
    }
}

题目来源