C code for Generate Parentheses 44 ms. How to make it more efficient


  • 0
    R
    int fact(int n) {
        if((n==0) || (n==1)) {
            return 1;
        }
        
        return fact(n-1) * n;
    }
    
    bool is_duplicate(char **str, char *check, int size) {
        for(int i=0; i<size; i++) {
            if(!strcmp(str[i], check)) {
                return true;
            }
        }
        return false;
    }
    
    char * insert_par_pos(char *str, int pos) {
        int len = strlen(str);
        char *par = malloc(sizeof(char) * (len+3));
        strncpy(par, str, len + 1);
        par[pos+1] = '\0';
        strncat(par, "()\0", len+3);
        strncat(par, &str[pos+1], (len+3));
        return par;
    }
    
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    char** generateParenthesis(int n, int* returnSize) {
        
        char **res;
        if(n == 0) {
            res = malloc(sizeof(char *) * 1);
            res[0] = malloc(sizeof(char *) * 3);
            strncpy(res[0], "()\0", 3);
            *returnSize = 1;
            return res;
        }
        
        char **p_res = generateParenthesis(n-1, returnSize);
        int res_sz = fact(n);
        res = malloc(sizeof(char *) * res_sz);
        
    
        if(n == 1) {
            return p_res;
        } else {
            int k = 0;
            for(int i=0; i<(*returnSize); i++) {
                for(int j=0; j<strlen(p_res[i]); j++) {
                    char *temp;
                    temp = insert_par_pos(p_res[i], j);
                    if(!is_duplicate(res, temp, k)) {
                        res[k] = temp;
                        k++;
                    }
                }
            }
            *returnSize = k;
        }
        
        return res;
    }

  • 1
    D
    void helper(char*** pppc, int*returnSize, int n, char* res, int level, int i, int index){
        if (index==2*n) {
            res[index] = '\0';
            (*returnSize)++;
            (*pppc) = (char**)realloc(*pppc, sizeof(char*)*(*returnSize+1));
            (*pppc)[*returnSize-1] = (char*)malloc(sizeof(char)*(2*n+1));
            strcpy((*pppc)[*returnSize-1], res);
            return;
        }
        if (i<n) {
            res[index] = '(';
            helper(pppc, returnSize, n, res, level+1, i+1, index+1);
        }
        if (level>0) {
            res[index] = ')';
            helper(pppc, returnSize, n, res, level-1, i, index+1);
        }
        
    }
    char** generateParenthesis(int n, int* returnSize) {
        char** ppc = (char**)malloc(sizeof(char*));
        *returnSize = 0;
        char* res = (char*)malloc(sizeof(char)*(2*n+1));
        helper(&ppc, returnSize, n, res, 0, 0, 0);
        return ppc;
    }
    

    my 0ms c solution


Log in to reply
 

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