给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
思路一：DFS+回溯
c语言解法
bool isPalindrome(char *s,int l,int r){
while(l<=r){
if(s[l++]!=s[r--])return false;
}
return true;
}
void dfs(char *s, int len, char ***res, int* returnSize, int** returnColumnSizes, char buf[][len +1], int idx)
{
int i;
if (*s == '\0') {
res[*returnSize] = (char**)malloc(sizeof(char*) * len);
for (i = 0; i < idx; i++) {
res[*returnSize][i] = (char*)malloc(sizeof(char) * (len + 1));
strcpy(res[*returnSize][i], buf[i]);
}
(*returnColumnSizes)[(*returnSize)++] = idx;
return;
}
int len2 = strlen(s);
for (i = 0; i < len2; i++) {
if (isPalindrome(s, 0, i) == true) { /* 子串满足回文后, 继续处理 */
strncpy(buf[idx], s, i + 1); /* 将子串复制到buf中, 增加结束符 */
buf[idx][i + 1] = '\0';
dfs(s + i + 1, len, res, returnSize, returnColumnSizes, buf, idx + 1);
}
}
}
char *** partition(char * s, int* returnSize, int** returnColumnSizes){
if (strlen(s) == 0) {
*returnSize = 0;
return NULL;
}
int len = strlen(s);
char ***res = (char***)malloc(sizeof(char**) * 32768);
char buf[len][len + 1]; /* 临时buf */
*returnSize = 0;
*returnColumnSizes = (int*)malloc(sizeof(int) * 32768);
dfs(s, len, res, returnSize, returnColumnSizes, buf, 0);
return res;
}分析：
本题要求出原字符串分割后的所有回文串，可以先编写判断回文串的函数ispalindrome，之后采用深度优先搜索和回溯的方法将所有字符串的子串求出，深度优先的边界条件设置为当遍历到字符串的结束符时结束，最后返回所有回文串
总结：
本题考察深度优先搜索的用法，注意回溯判断当字符串为回文串时回溯