C++ DFS solution - 6 msec


  • 0
    A
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) 
        {
            set<string> result;
            set<string> visited;
            if (s.length() > 0) {
               removeInvalidParentheses(s, result, visited);
            } else {
                result.insert(s);
            }
    
            return vector<string>(result.begin(), result.end());
        }
        
    protected:
        void removeInvalidParentheses(string &s, set<string> &result, set<string>& visited)
        {
            int leftCount = 0;
            int rightCount = 0;
            vector<int> rightPositions;
            vector<int> leftPositions;
            
            if (visited.find(s) != visited.end()) {
                return;
            }
            
            visited.insert(s);
            
            for (int i = 0; i < s.length(); ++i) {
                if ((s[i] == '(')) {
                    leftPositions.push_back(i);
                    ++leftCount;
                    
                } else if (s[i] == ')') {
                    rightPositions.push_back(i);
                    ++rightCount;
                    if (leftCount == rightCount) {
                        leftCount = rightCount = 0;
                        leftPositions.clear();
                        
                    } else if (rightCount > leftCount) {
                        vector<string> fixedStrings = getFixedStrings(s, rightPositions);
                        for (auto itr = fixedStrings.begin(), end = fixedStrings.end(); itr != end; itr++) {
                            removeInvalidParentheses(*itr, result, visited);
                        }
                        
                        return;
                    }
                }
            }
                     
            if (leftCount > rightCount) {
                vector<string> fixedStrings = getFixedStrings(s, leftPositions);
                for (auto itr = fixedStrings.begin(), end = fixedStrings.end(); itr != end; itr++) {
                    removeInvalidParentheses(*itr, result, visited);
                }
            } else if (leftCount == rightCount) {
               result.insert(s);
            }
        }
        
        vector<string> getFixedStrings(string &s, vector<int> &positions) {
            vector<string> strs;
            int lastPos = -1;
            for(auto itr = positions.begin(), end = positions.end(); itr != end; itr++) {
                if ((lastPos == -1) || (*itr != lastPos + 1)) {
                    string s2 = s;
                    s2.erase(*itr, 1);         
                    strs.push_back(s2);
                }
                
                lastPos = *itr;
            }
            
            return strs;
        }
    };
    

Log in to reply
 

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