C++ Depth limited DFS 3ms. Eliminate duplicates without hashmap.


  • 11
    C

    num1 and num2 stand for the number of '(' and ')' to remove respectively. Duplicates arise from consecutive '(' or ')'. We only get rid of the first one before going a level further.

    class Solution {
    private:
        bool isValid(string s) {
            int sum = 0;
            for(char &c : s) {
                if(c == '(') ++sum;
                else if(c == ')') --sum;
                if(sum < 0) return false;
            }
            return sum == 0;
        }
    public:
        vector<string> removeInvalidParentheses(string s) {
            int num1 = 0, num2 = 0;
            for(char &c : s) {
                num1 += c == '(';
                if (num1 == 0) {
                    num2 += c == ')';
                } else {
                    num1 -= c == ')';
                }
            }
            vector<string> ret;
            dfs(s, 0, num1, num2, ret);
            return ret;
        }
        void dfs(string s, int beg, int num1, int num2, vector<string> &ret) {
            if(num1 == 0 && num2 == 0) {
                if(isValid(s))
                    ret.push_back(s);
            } else {
                for(int i = beg; i < s.size(); ++i) {
                    string tmp = s;
                    if(num2 == 0 && num1 > 0 && tmp[i] == '(') {
                        if(i == beg || tmp[i] != tmp[i - 1]) {
                            tmp.erase(i, 1);
                            dfs(tmp, i, num1 - 1, num2, ret);
                        }
                    }
                    if(num2 > 0 && tmp[i] == ')') {
                        if(i == beg || tmp[i] != tmp[i - 1]) {
                            tmp.erase(i, 1);
                            dfs(tmp, i, num1, num2 - 1, ret);
                        }
                    }
                }
            }
        }
    };

  • 0
    N

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


  • 0
    C

    @neer1304 It's a depth limited dfs. The space complexity is liner to the search tree depth. The time complexity would be 2^depth, where depth = num1 + num2


  • 0
    W

    @cqnkxy why it is dfs, uh...i think it is bfs


  • 0
    C

    @winferr It's a dfs search not because I name the function dfs, but during the recursion I go a step further immediately when I find a next state to expand, instead of expanding all the feasible next states first.


  • 0
    B

    Thank you for the solution! It is great!
    I think in if(num2 == 0 && num1 > 0 && tmp[i] == '(') ,
    num2 == 0 is not needed!


  • 0
    C

    @BURIBURI It's true. But adding this line does give you a performance boost.


  • 0
    D
        void dfs(string s, int begin, int open, int close, vector<string> &res) {
            if(open == 0 && close == 0) {
                if(validParenthesis(s)) res.push_back(s);
            } else {
                for(int i = begin; i < s.size(); i++) {
                    string t = s;
                   if(close > 0 && t[i] == ')' || open > 0 && t[i] == '(') {
                        if(i == begin || t[i] != t[i - 1]) {
                            t.erase(i, 1);
    // Optimized a little bit here
                            if (close > 0) dfs(t, i, open, close - 1, res);
                            else if (open > 0) dfs(t, i, open - 1, close, res);
                        }
                    }                
                }            
            }
        }
    

Log in to reply
 

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