Just one thing should be concerned, accepted as best submission in C


  • 0

    As the title points out that the only thing that we should care about is that opening bracket should always be closed by closing brackets instead of the opposite and in the end since we will make sure the amount of both the opening and closing brackets is the same, so the result will definitely be valid; and since we will traverse all the possible paths, so the set will also be fetched.

    always close the opening brackets

    • space cost O(n2^n) each set will take 2n character and the amount of sets is obviously 2^n which in fact might fluctuate a little bit for the validity of the parentheses.
    • time cost O(n*2^n), traversing and collecting them! Dude! Be serious!

    void traverse(char*** arr, int* returnSize, char* stack, int top, int leftCount, int rightCount)
    {
        if(!leftCount && !rightCount)
        {
            *returnSize += 1;
            *arr = (char**)realloc(*arr, sizeof(char*)*(*returnSize));
            (*arr)[*returnSize-1] = (char*)malloc(sizeof(char)*(top+2));
            for(int i = 0; i <= top; i++)
                (*arr)[*returnSize-1][i] = stack[i];
            (*arr)[*returnSize-1][top+1] = '\0';
            return ;
        }
        if(leftCount)
        {
            stack[top+1] = '(';
            traverse(arr, returnSize, stack, top+1, leftCount-1, rightCount);
        }
        if(rightCount)
        {
            stack[top+1] = ')';
            traverse(arr, returnSize, stack, top+1, leftCount, rightCount-1);
        }
    }
    
    //AC - 0ms;
    char** generateParenthesis(int n, int* returnSize)
    {
        if(!n) return NULL;
        char **arr = (char**)malloc(sizeof(char*));
        *returnSize = 0;
        char* stack = (char*)malloc(sizeof(char)*2*n);
        int top = -1;
        int leftCount = n; 
        int rightCount = n;
        traverse(&arr, returnSize, stack, top, leftCount, rightCount);
        return arr;
    }

Log in to reply
 

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