Leetcode 301 Solution

This article provides solution to leetcode question 301 (remove-invalid-parentheses)
Categories:
Tags:
Access this page by simply typing in "lcs 301" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    bool isvalid(const string& s)
    {
        int cnt = 0;



        for (auto ch : s)
        {
            if (ch == '(')
                cnt++;
            else if (ch == ')')
                cnt--;



            if (cnt < 0)
                return false;
        }



        return cnt == 0;
    }
    vector<string> removeInvalidParentheses(string s) {
        queue<string> q;
        unordered_set<string> visited;
        vector<string> res;
        bool found = false;



        q.push(s);
        visited.insert(s);



        while (q.empty() == false)
        {
            auto str = q.front();
            q.pop();



            if (isvalid(str))
            {
                res.push_back(str);
                found = true;
            }



            if (found)
                continue;



            for (int i = 0; i < str.size(); i++)
            {
                if (str[i] == '(' || str[i] == ')')
                {
                    string next_str = str.substr(0, i) + str.substr(i + 1);



                    if (visited.find(next_str) != visited.end())
                        continue;



                    visited.insert(next_str);
                    q.push(next_str);
                }
            }
        }



        return res;
    }
};