Leetcode 括号匹配(Leetcode bracket matching)

括号表达式匹配的条件:从左往右,左括号个数大于等于右括号个数,且最后左右括号数相等。

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 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的翻版,但方法完全不一样。
看这条件 ,暴搜无疑了。
BFS:给定一个表达式,删除一个元素得到拓展表达式。

1 <= s.length <= 25
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;
    }
};
————————

Matching conditions for parenthesis expressions: from left to right, < strong > the number of left parentheses is greater than or equal to the number of right parentheses < / strong >, and the last number of left and right parentheses is equal.

LC 921. Add the least number of valid parentheses

Topic: add a minimum number of left or right parentheses to make the expression valid
method:
Greedy, encounter the right parenthesis, match if you can match, and add 1 to the answer if you can’t match.
Why doesn’t it prove that this is the least number of times

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 1963. Minimum number of swaps to balance strings

Title: the string is exactly composed of N / 2 open parentheses’ [‘and N / 2 closed parentheses’]’. Returns the minimum number of swaps required to make s a balanced string.
method:
Greedy. From front to back, match if you can, and exchange if you can’t.
Will not prove correct.

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. Remove invalid parentheses

Title: remove the minimum number of invalid parentheses to make the input string valid. All possible results are required to be returned.
method:
It seems to be a replica of 921, but the method is completely different.
Look at these conditions, there is no doubt about the violent search.
BFS: given an expression, delete an element to get an extended expression.

1 <= s.length <= 25
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. Remove invalid parentheses

Title: delete the least ‘(‘ or ‘)’ from the string (you can delete parentheses at any position) to make the remaining “parenthesis string” valid. Please return any legal string.
method:
Compared with the previous question, you only need to return any one.
Like adding, you can get greedy. Refer to 2 solutions, concise code, second understanding and detailed explanation — [1249]

Method 1: stack (from inside to outside)

Put the left bracket on the stack and the right bracket matches the top of the stack, so it matches from inside to outside.

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

Method 2: counting (from outside to inside)

Count the number of right parentheses first. Then go back and forth, try to match when encountering the left bracket, and try to match when encountering the right bracket.

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