題目

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:

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

Example 2:

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

Constraints:

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

我的思路

建立一個 Stack，loop 整個 String:

  • 遇到左括弧時將左括弧放入 Stack。
  • 遇到右括弧時檢查 Stack 是否還有左括弧:
    • 如果沒有就代表這邊需要加一個左括弧，所以結果要 +1
    • 如果有就代表這是一個 pair ，那就可以從 Stack 中 pop 掉這個左括弧

最後整個 String loop 過一遍以後，看看 Stack 中是否還有剩餘的左括弧，如果有這些左括弧每一個都需要配一個右括弧，所以返回結果要加上 Stack Size

程式碼

 1class Solution {
 2    public int minAddToMakeValid(String s) {
 3        Stack<Character> stack = new Stack<>();
 4        int sum = 0;
 5        for(char c : s.toCharArray()) {
 6            if (c == '(') {
 7                stack.add(c);
 8                continue;
 9            } 
10                
11            if (stack.empty()) {
12                sum++;
13            } else {
14                stack.pop();       
15            }
16        }
17        
18        return sum + stack.size();
19    }
20}