301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/  b

Solution:
will use BSF strategy. It is like brute force BSF, but will use a hash map to reduce duplicates; and also, this question ask for the minimum change, so once find the valid one, we just need to save all the valid strings in the same "layer" of the BSF.

Code:

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_map<string, int> m;
        queue<string> q;
        q.push(s);
        ++m[s];
        bool found = false;//label for valid layer.
        while(q.size()){
            string t = q.front();
            q.pop();
            if(isValid(t)){
                res.push_back(t);
                found = true;
            }
            if(found) continue;
            for(int i=0; i<t.size(); ++i){
                if(t[i] != '(' && t[i] != ')') continue;
                string temp = t.substr(0, i) + t.substr(i+1);//brute force BSF
                if(m.find(temp) == m.end()){
                    q.push(temp);
                    ++m[temp];
                }
            }
        }
        return res;
    }
private:
    bool isValid(string str){
        int ct = 0;
        for(auto a:str){
            if(a == '(') ++ct;
            if(a == ')' && ct-- == 0) return false;
        }
        return ct == 0;
    }
};

http://www.cnblogs.com/grandyang/p/4944875.html