Easy-understand 36ms c++ dfs

  • 1
    class Solution {
        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)))
            return ans;
        vector<string> removeInvalidParentheses(string s) {
            str = s;
            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()) {
            return temp;

Log in to reply

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