Easy-understand 36ms c++ dfs


  • 1
    M
    class Solution {
    public:
        string str;
        int len;
        map<string, vector<string> > all; // to store middle results
        
        // the answer for string starting at index pos, with additional left brackets
        vector<string> dfs(int pos, int left) {
            string key = to_string(pos)+"-"+to_string(left);
            if (all.find(key)!=all.end())
                return all[key];
            
            vector<string> ans, temp;
            if (left<0 || pos==len) {
                if (left==0) ans.push_back("");
                return ans;
            }
            
            int newLeft=left; // by default, in case str[pos] is letter
            if (str[pos]=='(') newLeft += 1; // in case we keep this '(', add one count of left brackets
            else if (str[pos]==')') newLeft -= 1; // in case we keep this ')', minus one count of left brackets
            
            for (auto& t : refine(dfs(pos+1, newLeft)))
                ans.push_back(str[pos] + t);
            
            if (str[pos]=='(' || str[pos]==')') // in case we remove '(' or ')', having the same num of left brackets
            	for (auto& t : refine(dfs(pos+1, left)))
            	    ans.push_back(t);
            
            all[key]=ans;
            return ans;
        }
        
        vector<string> removeInvalidParentheses(string s) {
            str = s;
            len=str.length();
            return refine(dfs(0, 0));
        }
        
        // helpers:
        int max(int a, int b) {
        	return a>b ? a : b;
    	}
        
        // keep strings with max length and remove duplicates
        vector<string> refine(vector<string> vec) {
            if (vec.empty())
                return vec;
                
            vector<string> temp;
            int maxlen=-1;
            for (auto& s : vec)
                maxlen=max(maxlen, s.length());
                
            set<string> seen;
            for (auto& s : vec)
                if (s.length()==maxlen && seen.find(s)==seen.end()) {
                    temp.push_back(s);
                    seen.insert(s);
                }
            return temp;
        }
    };

Log in to reply
 

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