My 0ms C solution


  • 0
    E

    The main idea is Manacher's Algorithm. This algorithm calculate LPS of each position in linear time. For string s, it makes a new helper string t and an array of palindromic substring length:

    s = abbac

    T = [ # a # b # b # a # c # ]

    P = [ 0 1 0 1 4 1 0 1 0 1 0 ]

    int steps[s.length+1] -- how many steps from s[0] to position i. Since every single char is a palindrome string, I init each step[i] with i.

    While Manacher's algorithm finds a new palindromic center and right, update each index between center and right, set it to min(step[mirrorIndex(i, center)]+1, step[i]).

    int minCut(char* s) {
        int slen = strlen(s), tlen = slen*2+1, i;
        if (slen <= 1)
            return 0;
    
        char *t = (char*)malloc(tlen); // helper string t
        int *p = (int*)malloc(tlen*sizeof(int)), *steps = (int*)malloc((slen+1)*sizeof(int));
    
        t[0] = '#';
        for (i = 0; i < slen; i++) {
            t[i*2+1] = s[i];
            t[i*2+2] = '#';
            steps[i] = i;
        }
        steps[slen] = slen;
    
        int center = 1, right = 2;
        p[0] = 0;
        p[1] = 1;
        
        for (i = 2; i < tlen; i++) {
            int mirror = center*2 - i;
            if (right > i && p[mirror] < right-i) {
                p[i] = p[mirror];
                continue;
            }
    
            int limit = min(i, tlen-i-1), n, j;
            for (n = right <= i ? 1 : right+1-i; n <= limit; n++) {
                if (t[i+n] != t[i-n])
                    break;
            }
    
            p[center = i] = --n;
            right = i + n;
    
            for (j = (i-n)/2; n >= 1; j++, n -= 2) { // update steps
                steps[j+n] = min(steps[j+n], steps[j]+1);
            }
        }
        
        int r = steps[slen]-1;
        free(t);
        free(p);
        free(steps);
        return r;
    }
    

    The complexity of Manacher's algorithm is O(n). But, since every time the center and right are changing, the updating of steps costs (newRight - newCenter) time, while Manacher's only spends (newRight - oldRight), a little bit more (right-i) makes this algorithm O(n^2).

    btw, the JS version was 145ms, while the Java used 300ms...


Log in to reply
 

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