代码随想录算法训练营第二十三天|Day23 回溯算法

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6

思路

char** path;
int pathTop;
char*** ans;
int ansTop = 0;
int* ansSize;
void copy() {char** tempPath = (char**)malloc(sizeof(char*) * pathTop);int i;for(i = 0; i < pathTop; i++) {tempPath[i] = path[i];}ans[ansTop] = tempPath;ansSize[ansTop++] = pathTop;
}
bool isPalindrome(char* str, int startIndex, int endIndex) {while(endIndex >= startIndex) {if(str[endIndex--] != str[startIndex++])return 0;}return 1;
}
char* cutString(char* str, int startIndex, int endIndex) {char* tempString = (char*)malloc(sizeof(char) * (endIndex - startIndex + 2));int i;int index = 0;for(i = startIndex; i <= endIndex; i++)tempString[index++] = str[i];tempString[index] = '\0';return tempString;
}
void backTracking(char* str, int strLen,  int startIndex) {if(startIndex >= strLen) {copy();return ;}int i;for(i = startIndex; i < strLen; i++) {if(isPalindrome(str, startIndex, i)) {path[pathTop++] = cutString(str, startIndex, i);}else {continue;}backTracking(str, strLen, i + 1);pathTop--;}
}char*** partition(char* s, int* returnSize, int** returnColumnSizes){int strLen = strlen(s);path = (char**)malloc(sizeof(char*) * strLen);ans = (char***)malloc(sizeof(char**) * 40000);ansSize = (int*)malloc(sizeof(int) * 40000);ansTop = pathTop = 0;backTracking(s, strLen, 0);*returnSize = ansTop;*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int i;for(i = 0; i < ansTop; ++i) {(*returnColumnSizes)[i] = ansSize[i];}return ans;
}

学习反思

1. 将输入的字符串转换为字符数组，以便于通过索引访问和取子串。
2. 定义一个辅助函数isPalindrome，使用双指针法判断子串是否为回文字符串。
3. 初始化结果数组result和切割方案数组path。
4. 定义回溯函数backtracking，传入参数startIndex表示当前要切割的子串的起始索引。
5. 终止条件为startIndex超过字符串长度，此时收集切割方案path并添加到结果数组result中。
6. 遍历从startIndex到字符串末尾的所有子串，判断子串是否为回文字符串。如果是，将子串添加到切割方案path中，然后递归调用backtracking函数来寻找下一个起始位置的子串。
7. 在递归调用之后，如果切割方案path非空，将最后一个元素弹出，进行回溯操作。
8. 最后调用backtracking函数，startIndex初始为0，完成递归回溯的过程。
9. 返回结果数组result。

在Swift中，使用数组来存储结果集和切割方案，通过append和removeLast方法来添加和移除元素。通过回溯算法，可以找到所有满足条件的切割方案。时间复杂度为O(N * 2^N)

总结

对回溯算法有了更深刻的认识，加油！！！