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(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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 <= 1000s[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)
}