A typical DFS and backtracking problem, a concise solution accepted with 8ms in C, well-explained


  • 1

    Without any crap! Hit the road!

    Since we have to collect all the possible sets that meet the requirements -> a palindrome; so traversing the whole possible paths will be definitely the case -> using DFS and backtracking seems to be on the table.

    • try from the start index of the string till any index latter and then check its validity - a palindrome? from the start index till the ending?
    • if so, we need to store it in a stack for latter collection and then traverse further starting from the previous ending index exclusively and begin the checking again and on and on till the start index is beyond the string;
    • at that time we are to collect the palindromes along the paths.

    Several stuff should be specified:

    • checking whether a string is palindrome is quite simple in C using pointer;
    • using DP might not help a lot since the checking process is quite fast while DP will require extra work to record and space allocation and so on.

    In the end, let's check its space and time consumption:

    • space cost O(n*2^n) -> one set of palindrome will take about O(n) but the amount of sets is dependent on the original string itself.
    • time cost O(n*2^n) -> collecting them while using the space to store them so the space and time cost should be linearly proportional; since the range can be varied a lot depending on the actual provided string so the performance might not be a problem.

    void traverse(char* s, int len, int begin, char** stack, int top, char**** arrs, int** colSizes, int* returnSize)
    {
        if(begin == len) //there is nothing left, collect the strings of a set;
        {
            *returnSize += 1;
            *colSizes = (int*)realloc(*colSizes, sizeof(int)*(*returnSize));
            int size = top+1;
            (*colSizes)[*returnSize-1] = size;
            *arrs = (char***)realloc(*arrs, sizeof(char**)*(*returnSize));
            (*arrs)[*returnSize-1] = (char**)malloc(sizeof(char*)*size);
            for(int i = 0; i < size; i++)
                (*arrs)[*returnSize-1][i] = stack[i];
            return ;
        }
        for(int i = begin; i < len; i++) //check each string that begin with s[begin];
        {
            int l=begin, r=i;
            while(l<r && s[l]==s[r]) l++, r--;
            if(l >= r) //it's a palindrome;
            {
                int size = i-begin+1;
                char *t = (char*)malloc(sizeof(char)*(size+1));
                *t = '\0';
                strncat(t, s+begin, size);
                stack[top+1] = t;
                traverse(s, len, i+1, stack, top+1, arrs, colSizes, returnSize); //collect the left;
            }
        }
    }
    
    //AC - 8ms;
    char*** partition(char* s, int** colSizes, int* returnSize)
    {
        if(!*s) return NULL;
        int len = strlen(s);
        *returnSize = 0;
        *colSizes = (char*)malloc(sizeof(char));
        char*** arrs = (char***)malloc(sizeof(char**));
        char** stack = (char**)malloc(sizeof(char*)*len);
        int top = -1;
        traverse(s, strlen(s), 0, stack, top, &arrs, colSizes, returnSize);
        return arrs;
    }

Log in to reply
 

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