本文主要是介绍力扣日记1.27-【回溯算法篇】131. 分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣日记：【回溯算法篇】131. 分割回文串
日期：2023.1.27
参考：代码随想录、力扣
131. 分割回文串
题目描述
难度：中等
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
题解
class Solution {
public:// 关键：将切割问题类比转换为组合问题(树状图)// 但切割与组合最大的不同在于横向遍历时，组合是从集合中取单个值，但切割是截取一个子串 -> for循环时，[startindex, i]表示当前截取的子串(左闭右闭)vector<vector<string>> results; // 组合的集合vector<string> path; // 存储回文子串的组合vector<vector<string>> partition(string s) {backtracking(s, 0);return results;}// 如何判断回文串(双指针，一个从头往后，一个从尾往前，对应相等则为回文串)bool isPalindrome(string s, int startindex, int endindex) {// 左闭右闭while (startindex < endindex) {if (s[startindex] != s[endindex]) {return false;}startindex++;endindex--;}return true;}// 回溯三部曲：// 参数：字符串s以及记录当前截取子串的起始位置startindex(从同一个集合中连续截取，因此需要startindex用于递归纵向遍历)void backtracking(string s, int startindex) {// 终止条件,startindex超过s长度if (startindex == s.size()) { // 左闭，相等即超过// startindex能到最后，说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)results.push_back(path);return;}// for循环找到回文子串[startindex, i]for (int i = startindex; i < s.size(); i++) {// 是回文子串则截取并递归后面的子串，否则往后遍历找回文子串if (isPalindrome(s, startindex, i)) {// 截取子串并存储path.push_back(s.substr(startindex, i - startindex + 1)); // 注意substr的参数是起始位置以及截取长度backtracking(s, i + 1); // 从i之后的子串递归[i+1, s.size()-1]// 回溯，弹出path.pop_back(); // 之后for向右遍历，尝试截取[startindex, i+1]子串}}}};
复杂度
时间复杂度: O(n * 2^n)
空间复杂度: O(n^2)
思路总结
思路完全参考代码随想录
- 本题实际上算是困难题目
- 难点有以下：
- 将切割问题抽象为组合问题，并转换为树状结构
- 如何模拟那些切割线（如何记录截取子串的始末位置）
- 切割问题中递归如何终止（终止条件）
- 在递归循环中如何截取子串（什么时候该递归，什么时候跳过）
- 如何判断回文
- 将切割问题抽象为组合问题，并转换为树状结构：
-
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。 - 但切割与组合最大的不同在于横向遍历时，组合是从集合中取单个值[i]，但切割是截取一个子串（即[startindex, i]）
-
- 如何模拟那些切割线（如何记录截取子串的始末位置）
- for循环时，用[startindex, i]表示当前截取的子串(左闭右闭)
- 递归时，startindex = i + 1表示对i之后的子串进行递归截取
- 切割问题中递归如何终止（终止条件）
- startindex超过s长度（由于左闭右闭，相等即超过）
- 因为startindex能到最后，说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)
- 在递归循环中如何截取子串（什么时候该递归，什么时候跳过）
- 这里是本题“分割回文串”的特征所在，即处理节点（push_back）时要先确保当前for循环要截取的子串是回文串，才能对后面的子串进行递归；否则应该是循环遍历直到当前子串是回文串或结束for循环
- 即递归与回溯，发生的条件是 当前子串是回文子串（类似于40. 组合总和 II中只有满足“当前取的值不重复”的条件才能递归是一样的。所以也可以写成
for(...) {// 不是回文串则跳过if (!isPalindrome(...)) {continue;}// 递归与回溯... }
- 如何判断回文子串:
- 双指针法， 一个从头往后，一个从尾往前，对应相等则为回文串
- TODO：动态规划优化判断回文子串
这篇关于力扣日记1.27-【回溯算法篇】131. 分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
