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)
}