⭐⭐⭐⭐⭐【BFS求最小次数】LeetCode 301. Remove Invalid Parentheses

不剪枝会超时
硬币找零
最小值的时候

题目描述

知识点

BFS+最小次数

结果

实现

码前思考

1. 看到这道题目我完全不知道该怎么写，即使我之前已经写过了一道关于 BFS求最小次数 的题目了。。。
2. 困扰我的可能就是怎么判断括号合法这个问题，我一直想着用栈来判断，但是我看了别人的题解，才发现原来可以直接通过count计数左右括弧来判断匹配情况，而且还可以提前终止！

代码实现

//类似于那个最小和的情况，我们使用层次代表最小的删除
//此处有一个判断括弧是否匹配的算法，这是需要注意的
//注意如何删除remove
//如何查找find
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        //用于在加入队列之前进行判断是否已经加入到队列之中了
        unordered_set<string> vis;
        vector<string> res;
        queue<string> q;
        q.push(s);
        vis.insert(s);
        int level=-1;
        bool flag = true;

        while(flag){
            level++;
            int size = q.size();
            for(int i=0;i<size;i++){
                string cur = q.front();
                q.pop();

                //判断是否合法
                if(judge(cur)){
                    flag=false;
                    res.push_back(cur);
                }else{
                    for(int j=0;j<cur.size();j++){
                        if(cur[j]=='('||cur[j]==')'){
                            string tmp = cur;
                            tmp.erase(tmp.begin()+j);
                            if(vis.find(tmp)==vis.end()){//粗心了
                                q.push(tmp);
                                vis.insert(tmp);
                            }
                        }
                    }
                } 
            }
        }

        return res;
    }

    bool judge(string& s){//传地址快一些
        int count=0;
        int size = s.size();
        for(int i=0;i<size;i++){
            if(s[i]=='('){
                count++;
            }else if(s[i]==')'){
                count--;
                if(count<0){
                    return false;//提前返回
                }
            }
        }
        return count==0;
    }
};

码后反思

1. 在不需要排序的情况下，使用unordered_set要比set更好；
2. 注意字符串的删除函数是str.erase(str.begin()+j)，这个函数算比较冷门了，里面传的一定是迭代器！但是也可以使用str.erase(pos,length)，这样就可以直接传下标了，注意要写length；
3. 要记下来判断括号匹配这个judge()函数，不一定要用到栈呢~~~
4. 为了避免超时，一定要使用一个集合来控制已经访问过的字符串！