括号表達式比對的條件：從左往右，左括号個數大于等于右括号個數，且最後左右括号數相等。
LC 921. 使括号有效的最少添加
題目：添加最少數目的左括号或右括号，使得表達式有效
方法：
貪心，遇到右括号，能比對就比對，不能比對就答案加1。
為什麼這是最少的次數就不會證明了...
class Solution {
public:
int minAddToMakeValid(string s) {
int left = 0, ans = 0;
for(char ch : s) {
if(ch == '(') left++;
else {
if(left == 0) ans++;
else left--;
}
}
return ans+left;
}
};
LC 1541. 平衡括号字元串的最少插入次數
題目：與上題92稍有不同，一個左括号要比對兩個連續的右括号。
方法：記錄左括号個數，遇到兩個右括号就比對掉，左括号/右括号不夠時都需要補充，同時答案加1
class Solution {
public:
int minInsertions(string s) {
int left = 0;
int i = 0, n = s.size();
int ans = 0;
while(i < n) {
// cout << i << " " << left << " " << ans << endl;
if(s[i] == '(') {left++; i++;}
else {
if(i < n-1 && s[i+1] == ')') i += 2; // 連續兩個'('
else { // 隻有一個'('，補一個
i += 1;
ans++;
}
if(left) left--;
else ans++; // 補個左括号
}
}
return ans + left*2;
}
};
LC 1963. 使字元串平衡的最小交換次數
題目：字元串 恰好 由 n / 2 個開括号 '[' 和 n / 2 個閉括号 ']' 組成。傳回使 s 變成 平衡字元串 所需要的 最小 交換次數。
貪心。從前往後，能比對就比對，不能比對就交換。
不會證明正确性。
class Solution {
public:
int minSwaps(string s) {
int i = 0, j = s.size()-1;
int cnt = 0, ans = 0;
for(char ch : s) {
if(ch == '[') cnt++;
else {
if(cnt == 0) {ans++; cnt++;}
else cnt--;
}
}
return ans;
}
};
LC 301. 删除無效的括号
題目：删除最小數量的無效括号，使得輸入的字元串有效。要求傳回所有可能的結果。
看似是921的翻版，但方法完全不一樣。
看這條件
1 <= s.length <= 25
，暴搜無疑了。
BFS：給定一個表達式，删除一個元素得到拓展表達式。
class Solution {
public:
bool check(const string& s) {
int left = 0;
for(char ch : s) {
if(ch == '(') left++;
if(ch == ')') left--;
if(left < 0) return false;
}
return left==0;
}
vector<string> removeInvalidParentheses(string s) {
bool flag = false;
vector<string>res;
queue<string>q;
unordered_set<string>vis;
q.push(s);
vis.insert(s);
while(!q.empty()) { // BFS
cout << "size: " << q.size() << endl;
int size = q.size();
for(int i = 0;i < size;i++) { // 層次周遊
string s = q.front();q.pop();
cout << s << endl;
if(check(s)) {
res.push_back(s);
flag = true;
}
if(flag) continue; // 如果已經找到，都不用擴充了
for(int j = 0;j < s.size();j++) {
if(s[j] != '(' && s[j] != ')') continue;
string new_s = s.substr(0, j) + s.substr(j+1);
if(!vis.count(new_s)) {
vis.insert(new_s);
q.push(new_s);
}
}
}
if(flag) break; // 本輪已經找到了
}
return res;
}
};
LC 1249. 移除無效的括号
題目：從字元串中删除最少數目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字元串」有效。請傳回任意一個合法字元串。
與上一題相比，隻需要傳回任意一個。
和添加一樣，可以貪心得到。參考 2種解法,簡潔代碼,秒懂詳解--[1249]
方法一：棧（由内向外）
把左括号入棧，右括号取棧頂比對，是以是從内向外比對。
class Solution {
public:
string minRemoveToMakeValid(string s) {
vector<int>removing; // 當做棧
for(int i = 0;i < s.size();i++) {
if(s[i] == '(') removing.push_back(i); // 記錄左括号的位置
if(s[i] == ')') {
if(removing.size() > 0) removing.pop_back();
else s[i] = '*';
}
}
for(int idx : removing) s[idx] = '*';
s.erase(remove(s.begin(), s.end(), '*'), s.end());
return s;
}
};
方法二：計數（由外向内）
先統計右括号個數。再前往後周遊，遇到左括号嘗試比對，遇到右括号也先嘗試比對。
class Solution {
public:
string minRemoveToMakeValid(string s) {
int left = 0, right = count(s.begin(), s.end(), ')');
string res = "";
for(char& ch : s) {
if(ch == '(') {
if(right > 0) { // 如果有右括号，就一定能比對
left++;
right--;
res += ch;
}
}
else if(ch == ')') {
if(left > 0) { // 比對掉一個
left--;
res += ch;
}
else right--; // 删除右括号，目前右括号太多了
}
else res += ch;
}
return res;
}
};
LC 678. 有效的括号字元串
題目：在普通的括号比對的基礎上引入*号，判斷是否有效
方法：維護一段左括号的範圍[a, b]。遇到'(' a,b都加1，遇到')' a,b都減1，遇到'*' a減1 b加1
class Solution {
public:
bool checkValidString(string s) {
int a = 0, b = 0; // 左括号的可能範圍[a, b]
for(char& ch : s) {
if(ch == '(') a++,b++;
else if(ch == ')') {
if(b < 1) return false;
a = max(a-1, 0);
b--;
} else {
a = max(a-1, 0);
b++;
}
}
return a == 0;
}
};
LC 2116. 判斷一個括号字元串是否有效
方法：同上題678，能修改的就相當于'*'，但是像'*', '***'，這些也不行，因為這裡的'*'不能為空，但是可以直接用奇數長度判掉。
class Solution {
public:
bool checkValidString(string s) {
int a = 0, b = 0; // 左括号的可能範圍[a, b]
for(char& ch : s) {
if(ch == '(') a++,b++;
else if(ch == ')') {
if(b < 1) return false;
a = max(a-1, 0);
b--;
} else {
a = max(a-1, 0);
b++;
}
}
return a == 0;
}
bool canBeValid(string s, string locked) {
int n = s.size();
if(n & 1) return false;
for(int i = 0;i < n;i++) {
if(locked[i] == '0') s[i] = '*';
}
return checkValidString(s);
}
};
個性簽名：時間會解決一切