做外贸兼职的网站设计,软件开发工程师的就业前景,东莞工程网站建设,做网站延期交付了力扣日记#xff1a;【回溯算法篇】131. 分割回文串 日期#xff1a;2023.1.27 参考#xff1a;代码随想录、力扣 131. 分割回文串
题目描述 难度#xff1a;中等 给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可…力扣日记【回溯算法篇】131. 分割回文串 日期2023.1.27 参考代码随想录、力扣 131. 分割回文串
题目描述 难度中等 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1 输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2 输入s “a” 输出[[“a”]] 提示
1 s.length 16s 仅由小写英文字母组成
题解
class Solution {
public:// 关键将切割问题类比转换为组合问题(树状图)// 但切割与组合最大的不同在于横向遍历时组合是从集合中取单个值但切割是截取一个子串 - for循环时[startindex, i]表示当前截取的子串(左闭右闭)vectorvectorstring results; // 组合的集合vectorstring path; // 存储回文子串的组合vectorvectorstring 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之后的子串递归[i1, s.size()-1]// 回溯弹出path.pop_back(); // 之后for向右遍历尝试截取[startindex, i1]子串}}}};复杂度
时间复杂度: 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动态规划优化判断回文子串
