Recursive DFS-solution accepted as best 0ms in C --> well-explanation


  • 3

    We are going to take three steps to make this problem easy enough to solve and in the end we will have the <font color="#00bb00">best solution</font>:

    Step 1 -> very intuitive solution

    Traverse the string from the very beginning till the end and try each character -> <font color="#bb0000">remove it or not remove it</font>, to determine whether the rest is solvable using DFS.

    • but there is a definitely problem, it's a brute-force method and in this case it will absolutely tumble into TLE since its time cost is O(n*2^n).

    Step2 -> using extra variable to reduce the complexity dramatically

    Why should we have to try each character since most of them can be ignored? But how to actually and simply reduce the complexity?

    • brackets come in pair, so there are quite limited left and right brackets should be removed while all others remain; huh? this will dramatically save us lots of time when the searching depth are constrained to the difference between the amount of left and right brackets -> time cost now is O(n^k) -> k is the difference between the amount of left and right brackets.

    Bang! Good choice! Love this!

    Step3 -> why there should be step3?

    Okay, now since the problem might already be solved, but there is also a little more we can do to make it better. While we are searching and trying each path encountering left and right bracket in step 2 we have to check the validity of the string at the end of the search (what is the end of the search? it's when the difference between left and right brackets are zero -> which specifically means the amount of left and right brackets are exactly the same). This checking validity process is quite tedious and time-consuming using a stack maybe, so that's why we need step 3 to remove this tricky little sub-problem.

    • we are to use another variable pair to record the state between left and right brackets (not remove a left bracket will increase pair while not remove a right will decrease it but -> before not-remove a right bracket we have to first check the pair -> is it decrease-able? -> that's the key we can make sure the final result will be a valid left-right-parentheses string -> needless for further checking -> awesome, isn't it?) when traversing further -> we have to check whether the removing process should be done or not.

    At last the complexity is dramatically shrunk -> real O(n^k)

    One more thing should also be aware that the result string should be unique in the return sets so when we are collecting the string we have to check whether it's been collected or not -> since we are using C instead of C++ or Java or some other high-level ones whose set objects might easily handle this issue -> since we are C fighters, that's a little stuff we need to do here ^^

    Bang! End of Story!

    • space complexity O(n^2), since the amount of the sets will be around O(n) -> it's a guess without further accurate calculation;
    • time complexity O(n^k), after the pruning operations the complexity will be determined by the difference between the amount of left and right brackets.

    void traverse(char* s, int len, int start, int left, int right, int pair, char* stack, int top, char*** arr, int *returnSize)
    {
        if(start == len)
        {
            if(!left && !right && !pair)
            {
                int size = top+1;
                char *t = (char*)malloc(sizeof(char)*(size+1));
                for(int i = 0; i < size; i++)
                    t[i] = stack[i];
                t[size] = '\0';
                int i = 0;
                while(i < *returnSize) //remove duplicates;
                {
                    if(!strcmp(t, (*arr)[i]))
                        break;
                    i++;
                }
                if(i == *returnSize) //add a bran-new string;
                {
                    *returnSize += 1;
                    *arr = (char**)realloc(*arr, sizeof(char*)*(*returnSize));
                    (*arr)[*returnSize-1] = t;
                }
            }
            return ;
        }
        char c = s[start];
        if(c == '(')
        {
            if(left) //try to remove it;
                traverse(s, len, start+1, left-1, right, pair, stack, top, arr, returnSize);
            stack[top+1] = c; //try to add it as a pair;
            traverse(s, len, start+1, left, right, pair+1, stack, top+1, arr, returnSize);
        }
        else if(c == ')')
        {
            if(right) //try to remove it;
                traverse(s, len, start+1, left, right-1, pair, stack, top, arr, returnSize);
            if(pair) //try to use it as the other half of a pair;
            {
                stack[top+1] = c;
                traverse(s, len, start+1, left, right, pair-1, stack, top+1, arr, returnSize);
            }
        }
        else //just collect since it's not brackets;
        {
            stack[top+1] = c;
            traverse(s, len, start+1, left, right, pair, stack, top+1, arr, returnSize);
        }
    }
    
    //AC - 0ms;
    char** removeInvalidParentheses(char* s, int* returnSize)
    {
        char** arr = (char**)malloc(sizeof(char*));
        *returnSize = 0;
        int left=0, right=0;
        for(int i = 0; s[i]; i++) //find out how many opening and closing brackets should be removed;
        {
            if(s[i] == '(') left++;
            else if(s[i] == ')')
            {
                if(left) left--;
                else right++;
            }
        }
        int len = strlen(s);
        char *stack = (char*)malloc(sizeof(char)*len);
        int top = -1;
        traverse(s, len, 0, left, right, 0, stack, top, &arr, returnSize);
        return arr;
    }

  • 0

    Nice solution, but I think you make mistakes in analyzing the time complexity at some steps.

    For example, step 1 time cost is O(n^n)? no way. The most dumbest solution is to check each of the possible substrs, which has 2^n possibilities. Even it takes O(n) time to check each one, the time complexity can at most be O(n*2^n), which is far less than O(n^n).


  • 0

    Yeah, you're right, man. Thanks to point it out. My bad, I've updated it.


Log in to reply
 

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