From simple solution to best in C, well-explained


  • 1

    Basically this problem is quite easy as long as we know what palindrome is. So there is a basic solution traversing from the very beginning to the end to check each case including odd and even long palindrome.

    • space cost O(n) the length of the result palindrome;
    • time cost O(n^2), since we have to check each index and then search for the palindrome starting from that index including odd and even;

    But still the performance is not that bad compared with other submissions accepted with 20ms.


    void check(char* s, int len, int l, int r, int* start, int* maxLen)
    {
        while(l>-1 && r<len && s[l]==s[r]) l--, r++;
        int len0 = r-l-1;
        if(len0 > *maxLen)
        {
            *maxLen = len0;
            *start = l+1;
        }
    }
    
    //AC - 20ms;
    char* longestPalindrome(char* s)
    {
        int len = strlen(s);
        if(len < 2) return s;
        int start = 0;
        int maxLen = 0;
        for(int i = 0; i < len-1; i++)
        {
            check(s, len, i, i, &start, &maxLen);
            check(s, len, i, i+1, &start, &maxLen);
        }
        char* t = (char*)malloc(sizeof(char)*(maxLen+1));
        memcpy(t, s+start, sizeof(char)*maxLen);
        t[maxLen] = '\0';
        return t;
    }
    

    Now let's try to tune it for betterment, actually we truly do not need to check till the end since we can record the max length before traversing then

    i < len-1 && len-i > maxLen/2;

    should be the case to swipe the redundant searching and now it's performance improved by 40% accepted with 12ms beating most submissions.


    void check(char* s, int len, int l, int r, int* start, int* maxLen)
    {
        while(l>-1 && r<len && s[l]==s[r]) l--, r++;
        int len0 = r-l-1;
        if(len0 > *maxLen)
        {
            *maxLen = len0;
            *start = l+1;
        }
    }
    
    //AC - 12ms;
    char* longestPalindrome(char* s)
    {
        int len = strlen(s);
        if(len < 2) return s;
        int start = 0;
        int maxLen = 0;
        for(int i = 0; i < len-1 && len-i > maxLen/2; i++)
        {
            check(s, len, i, i, &start, &maxLen);
            check(s, len, i, i+1, &start, &maxLen);
        }
        char* t = (char*)malloc(sizeof(char)*(maxLen+1));
        memcpy(t, s+start, sizeof(char)*maxLen);
        t[maxLen] = '\0';
        return t;
    }
    

    Till now, almost done. But it is not actually. There are so many duplicates in the string which will dramatically increase the burden of repeated checking so we have to handle them in each round.

    ignore them and accordingly update the next start index

    after moving over them the left index and the right index should be pointing to the first different characters (different from the duplicate) and then we do checking as we usually do -> respectively to the left and right direction till the end. And now there is no need checking odd or even -> even case will be pruned ^^.

    After this pruning the performance now becomes awesome, accepted with 0ms!


    char* longestPalindrome(char* s)
    {
        int len = strlen(s);
        if(len < 2) return s;
        int start=0, maxLen=0;
        int l=0, r=0;
        for(int i = 0; i<len && len-i>maxLen/2;)
        {
            l = r = i;
            while(r<len-1 && s[r+1]=s[r]) r++; //remove all the duplicates but l remains the same, only the non-duplicate should be checked with l -> now there will no even or odd length palindrome problem;
            i = r+1; //move to the next non-duplicate for a new start;
            while(l>0 && r<len-1 && s[r+1]==s[l-1]) l--, r++;
            int len0 = r-l-1;
            if(len0 > maxLen)
            {
                maxLen = len0;
                start = l;
            }
        }
        char* t = (char*)malloc(sizeof(char)*(maxLen+1));
        memcpy(t, s+start, sizeof(char)*maxLen);
        t[maxLen] = '\0';
        return t;
    }

  • 0

    Very nice! I haven't use C for a long time. Thanks for you solution I know where I made a mistake. I forget to add '\0' at the last position.


  • 0
    Z

    Got wrong when use strncpy() in case "dddddd", I think there is something wrong with '\0', but not sure...Any idea?


Log in to reply
 

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