921. Minimum Add to Make Parentheses Valid

Medium
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 ')'.

解題

func minAddToMakeValid(s string) int {
stack := make([]byte, 0)
​
for i:=0; i<len(s); i++ {
// 先將括號一個個從頭到尾推入
stack = append(stack, s[i])
​
if len(stack) == 0 {
continue
}
// 每次都檢查是否成對,是的話將這對括號拿掉
for len(stack) >= 2 {
top := stack[len(stack) - 1]
second := stack[len(stack)-2]
​
if second == '(' && top == ')' {
stack = stack[:len(stack)-2]
} else {
break
}
}
}
​
return len(stack)
}