C++: 3ms DFS without generating duplicates. Maybe easy to understand?


  • 0
    W

    This problem can be solved via DFS (backtracking) approach. A challenge will be the duplicate of valid parentheses being generated. For example, given string "())", removal of either the first or second ')' yields the same result. This problem arises when there are continuous '('s or ')'s. To eliminate such duplicates, we can store the results into an unordered_set.

    We can also eliminate such duplicates when handling continuous '(' and ')'s. How? Suppose there are n continuous '('s starting at position pos. Among these n'('s, the number of '('s being kept could be 0, 1, ..., n, which corresponds to the number of removals n, n-1, ... , 0. Then we go to position pos+n directly by traversing all these (n+1) possibilities. For example, for string "(a(()))", suppose the intermediate result is "(a" when we meet two consecutive '('s. We then deliver 3 intermediate results "(a", "(a(", and "(a((" to position 4, respectively. This approach will avoid duplicates.

    The mechanism of avoiding duplicates is not obvious as it looks like. Suppose we have "~~~))*))", where '*' represents a char rather than ')', and '~' any characters. During DFS, if we do not keep '*', then keeping "))" before '*' and removing "))" after '*' is equivalent to removing it after '*' while keeping it after. If so, the uniqueness of the results using this approach would fail. However, this case doesn't hold:

    • If '*' is not a parenthesis, we can't remove it. "))*'' and "*))" are not identical.
    • If '*' is ')', we can exclude it from intermediate result during DFS. The results may contain "))", either before or after '('. However, these two solutions are not optimal: why not we keep the "))" before '(' and at the same time keeping '(' itself and a single ')' after that, in order to avoid removing this pair?

    The main function is as follows. We first calculate how many '(' and ')' will be removed when using minimum removal. The results are stored into lrem and rrem (l and r indicates direction of bracket, left or right. And rem represents remaining.) During DFS, these two variables indicate how many removal operations could be conducted.

        vector<string> removeInvalidParentheses(string s) {
            string path;
            vector<string> res;
            int lrem = 0;
            int rrem = 0;
            for(auto c : s) {
                if(c == '(')
                    lrem ++;
                else if(c == ')') {
                    if(lrem > 0)
                        lrem --;
                    else
                        rrem ++;
                }
            }
            helper(s, 0, path, res, 0, lrem, rrem);
            
            return res;
        }
    

    The DFS helper function is as follows. When we meet a '(' or a ')', we count the number of its continuous occurrence. k-1 is the last occurrence. nLeft is the number of '('s that are unpaired till now.

        void helper(string& s, int pos, string& path, vector<string>& res, int nLeft, int lrem, int rrem) {
            if(nLeft > s.length() - pos || lrem < 0 || rrem < 0 || nLeft < 0) // [pos, n - 1] can provide n - pos ')'s
                return;
            if(pos >= s.length()) {
                res.push_back(path);
                return;
            }
            const string path_init(path);
            if(s[pos] != ')' && s[pos] != '(') { // Just keep it.
                path += s[pos];
                helper(s, pos + 1, path, res, nLeft, lrem, rrem);
                path.pop_back();
            }
            else if(s[pos] == '(') {
                int k = pos + 1;
                while(k < s.length() && s[k] == '(') {
                    k ++;
                }
                
                for(int i = 0; i <= k - pos; i ++) { // i: number of '(' being kept
                                                     //(k-pos-i) - number of removals from (k-pos) '('s
                    helper(s, k, path, res, nLeft + i, lrem - (k-pos-i), rrem);  // keep '('
                    path.push_back(s[pos]);
                }
                path = path_init;
            }
            else {
                int k = pos + 1;
                while(k < s.length() && s[k] == ')') {
                    k ++;
                }
                
                for(int i = 0; i <= k - pos; i ++) { // i: number of ')' being kept
                                                     //(k-pos-i) - number of removals from (k-pos) ')'s
                    helper(s, k, path, res, nLeft - i, lrem, rrem - (k-pos-i));  // keep '('
                    path.push_back(s[pos]);
                }
                path = path_init;
            }
        }
    

Log in to reply
 

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