921. Minimum Add to Make Parentheses Valid

Link: https://leetcode.com/problems/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:

Input: "())"
Output: 1

Example 2:

Input: "((("
Output: 3

Example 3:

Input: "()"
Output: 0

Example 4:

Input: "()))(("
Output: 4

Note:

• S.length <= 1000
• S only consists of ‘(‘ and ‘)’ characters.

---

題目翻譯:

給定一個’（’和’）’括號的字符串 S，我們添加最小數量的括號（’（’或’）’，並在任何位置），以便得到的括號字符串有效。

形式上，括號字符串是有效的，當且僅當：

• 它是空字符串，或者
• 它可以寫成 AB（與 B 連接），其中 A 和 B 是有效字符串，或
• 它可以是寫為（A），其中 A 是有效字符串。

給定一個括號字符串，返回我們必須添加的最小括號數，以使結果字符串有效。

程式思路:

蠻簡單的題目，不知道為甚麼分類在中等難度。

class Solution {
public:
    int minAddToMakeValid(string S) {
        int p = 0,err = 0;;
        for(auto c : S)
        {
            if(c == '(')
                p++;
            else if(c == ')')
                p--;
            if(p < 0)
            {
                err ++;
                p = 0;
            }
        }
        return p + err ;
    }
};