题目

leetcode 131
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

代码

void partition__(char *s, int start, int len, int **dp, char **str, int k, char ***res, int *returnSize, int **returnColumnSizes) {
    if (start == len) {
        res[*returnSize] = (char **)malloc(sizeof(char *) * k);
        for (int i = 0; i < k; i++) {
            int size = strlen(str[i]);
            res[*returnSize][i] = (char *)malloc(sizeof(char) * (size + 1));
            strcpy(res[*returnSize][i], str[i]);
            res[*returnSize][i][size] = '\0';
        }
        (*returnColumnSizes)[*returnSize] = k;
        (*returnSize)++;
        return ;
    }
    
    for (int i = start; i < len; i++) {
        if (dp[start][i] == 0) continue ;
        strncpy(str[k], s + start, i - start + 1);
        str[k][i - start + 1] = '\0';
        partition__(s, i + 1, len, dp, str, k + 1, res, returnSize, returnColumnSizes);
    }
}
char *** partition(char * s, int* returnSize, int** returnColumnSizes){
    int len = strlen(s);
    *returnSize = 0;
    if (len == 0) return 0;
    int **dp = (int **)malloc(sizeof(int *) * len);
    char **str = (char **)malloc(sizeof(char *) * len);
    for (int i = 0; i < len; i++) {
        dp[i] = (int *)malloc(sizeof(int) * len);
        str[i] = (char *)malloc(sizeof(char) * (len + 1));
    }
    for (int r = 0; r < len; r++) {
        for (int l = 0; l <= r; l++) {
            if (s[l] == s[r] && ((r - l < 2) || dp[l + 1][r - 1]))
                dp[l][r] = 1;
            else dp[l][r] = 0;
        }
    }
    #define MAX 1000000
    char ***res = (char ***)malloc(sizeof(char **) * MAX);
    (*returnColumnSizes) = (int *)malloc(sizeof(int) * MAX);
    partition__(s, 0, len, dp, str, 0, res, returnSize, returnColumnSizes);
    return res;
}