Remove Invalid Parentheses

1, queue, hash

2，遍历当前层，如果有valid的str，就扫描完当前层就结束；

3，否则的话，就遍历每一个str在去掉每一个char的情况，把他们加入queue

4，如果当前层有符合要求的话，下一层的部分情况有可能在queue里，但是不影响，因为如果去除n的字符有valid的，那么下一层valid的至少要去掉n-2个字符，所以扫描n-1个字符那一层的时候不会有valid的结果。

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

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int n = s.length();
        vector<string> ret;

        if(n == 0)
        {
            ret.push_back("");
            return ret;
        }

        list<string> queue;
        unordered_set<string> hash;
        queue.push_back(s);
        hash.insert(s);

        bool found = false;

        while(!queue.empty())
        {
            string temp = queue.front();
            queue.pop_front();

            if(isValid(temp))
            {
                ret.push_back(temp);
                found = true;
            }

            if(found == true)
            {
                continue;
            }

            for(int i = 0; i<temp.length(); i++)
            {
                if(temp[i] != '(' && temp[i] != ')')
                {
                    continue;
                }

                string newstr = temp.substr(0, i) + temp.substr(i+1);
                //cout<<newstr<<endl;

                if(hash.find(newstr) == hash.end())
                {
                    queue.push_back(newstr);
                    hash.insert(newstr);
                }
            }
        }

        if(ret.empty())
        {
            ret.push_back("");
        }

        return ret;
    }

    bool isValid(string s)
    {
        int count = 0;
        for(char c : s)
        {
            if(c == '(')
            {
                count++;
            }
            else if(c == ')')
            {
                count--;
            }

            if(count < 0)
            {
                return false;
            }
        }

        return count == 0;
    }
};