---

題目

只有滿足下面幾點之一，括號字符串才是有效的：

• 它是一個空字符串，或者
• 它可以被寫成 AB （A 與 B 連接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被寫作 (A)，其中 A 是有效字符串。

返回 為使結果字符串 s 有效而必須添加的最少括號數。

示例 1：

輸入：s = “())”
輸出：1

示例 2：

輸入：s = “(((”
輸出：3

---

解析

題目難度其實配不上中等二字，棧 or 貪心都可以解決，本篇博客旨在記錄評論區中見到的一個有趣想法。

貪心

class Solution {
public:int minAddToMakeValid(string s) {int num_left = 0;int res = 0;for(char i : s){if(i == '('){num_left++;}else{ // i == )if(num_left > 0) num_left--;else res++;}}return res += num_left;}
};

趣解

class Solution {
public:int minAddToMakeValid(string s) {while(s.find("()") != s.npos) {// 將（）替換為空字符串，并循環這一行為直至沒有成對括號出現s = s.replace(s.find("()"),2,"");}return s.size();}
};

循環消去 s 中的匹配括號，剩下的當然是不匹配的括號，也就是需要加多少個括號才能讓它們匹配啦~