Share my c++ bfs solution 4ms


  • 6
    Y
    class Solution {
    public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> ans;
        if (s.size() == 0) {
            ans.push_back("");
            return ans;
        }
        
        deque<string> queue;
        unordered_set<string> exists;
        queue.push_back(s);
        while (!queue.empty()) {
            string target_str = queue.front();
            queue.pop_front();
            // cut from 172ms to 92ms
            if (exists.find(target_str) != exists.end()) {
                continue;
            }
            // cut from 16 to 4ms
            exists.insert(target_str);
            int invalid_point = findInvalidPoint(target_str);
            if (invalid_point == -1) {
                ans.push_back(target_str);
                continue;
            }
            int start = 0;
            int limit = target_str.size();
            if (target_str[invalid_point] == LC) {
                start = invalid_point;
            } else {
                limit = invalid_point + 1;
            }
            for (int i = start; i < limit; ++i) {
                if (target_str[i] != target_str[invalid_point]) {
                    continue;
                }
                // cut from 92ms to 16ms, no need to search 
                if (i != start && target_str[i-1] == target_str[i]) {
                    continue;
                }
                string tmp_s = target_str.substr(0, i);
                if (i != target_str.size() - 1) {
                    tmp_s.append(target_str.substr(i+1, target_str.size()));
                }
                queue.push_back(tmp_s);
            }
        }
        
        return ans;
    }
    private:
    const char LC = '(';
    const char RC = ')';
    int findInvalidPoint(string& s) {
        stack<pair<char, int> > st;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == LC) {
                st.push(pair<char, int>(s[i], i));
            } else if (s[i] == RC) {
                if (st.size() == 0) {
                    return i;
                } 
                st.pop();
            }
        }
        int top = -1;
        if (!st.empty()) {
            top = st.top().second;
            st.pop();
        }
        return top;
    }
    };

  • 0
    N

    What would be the time and space complexity for this solution ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.