LeetCode #132 Palindrome Partiti

typedef struct{
    int location;
    int length;
}* Range;

Range MakeRange(int loc, int len) {
    Range r = (Range)malloc(sizeof(*r));
    r->location = loc;
    r->length = len;
    return r;
}

bool is_palindromic(char *s, Range range) {
    int i = range->location, j = range->location + range->length - 1;
    while (i < j && s[i] == s[j]) {
        I++;
        j--;
    }
    return i >= j;
}

int find_palindrome_start(char *s, int start, int end) {
    Range range = MakeRange(start, end - start + 1);
    while (!is_palindromic(s, range)) {
        range->location++;
        range->length--;
    }
    return range->location;
}

int min_cut_in_range(char *s, Range range) {
    int n = range->length;
    int *cuts = (int*)malloc((n + 1) * sizeof(*cuts));
    cuts[0] = cuts[1] = 0;
    for (int i = range->location + 2; i <= range->location + range->length; i++) {
        int start = find_palindrome_start(s, range->location, i - 1);
        if (start == range->location) {
            cuts[i - range->location] = 0;
        } else {
            if (start == i - 1) {
                cuts[i - range->location] = cuts[i - 1 - range->location] + 1;
            } else {
                int take = cuts[start - range->location] + 1;
                int drop = cuts[start + 1 - range->location] + (is_palindromic(s, MakeRange(start + 1, i - 1 - (start + 1) + 1)) ? 1 : 2);
                int min = take < drop ? take : drop;
                for (int j = start + 1; j <= i - 1; j++) {
                    if (is_palindromic(s, MakeRange(j, i - 1 - j + 1))) {
                        take = cuts[j - range->location] + 1;
                        drop = (j == i - 1) ? INT_MAX : (cuts[j + 1 - range->location] + (is_palindromic(s, MakeRange(j + 1, i - 1 - (j + 1) + 1)) ? 1 : 2));
                        int tmin = take < drop ? take : drop;
                        if (tmin < min) { min = tmin; }
                    }
                }
                cuts[i - range->location] = min;
            }
        }
    }
    return cuts[n];
}

int minCut(char * s) { return min_cut_in_range(s, MakeRange(0, (int)strlen(s))); }