分割回文串

但切割与组合最大的不同在于横向遍历时组合是从集合中取单个值但切割是截取一个子串

for循环时[startindex,

i]表示当前截取的子串(左闭右闭)vectorvectorstring

results;

如何判断回文串(双指针一个从头往后一个从尾往前对应相等则为回文串)bool

isPalindrome(string

false;}startindex;endindex--;}return

true;}//

参数字符串s以及记录当前截取子串的起始位置startindex(从同一个集合中连续截取因此需要startindex用于递归纵向遍历)void

backtracking(string

startindex能到最后说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)results.push_back(path);return;}//

i]for

截取子串并存储path.push_back(s.substr(startindex,

startindex

注意substr的参数是起始位置以及截取长度backtracking(s,

1);

将切割问题抽象为组合问题并转换为树状结构如何模拟那些切割线如何记录截取子串的始末位置切割问题中递归如何终止终止条件在递归循环中如何截取子串什么时候该递归什么时候跳过如何判断回文

将切割问题抽象为组合问题并转换为树状结构

组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个…。

切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段…。

但切割与组合最大的不同在于横向遍历时组合是从集合中取单个值[i]但切割是截取一个子串即[startindex,

for循环时用[startindex,

startindex超过s长度由于左闭右闭相等即超过因为startindex能到最后说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)

这里是本题“分割回文串”的特征所在即处理节点push_back时要先确保当前for循环要截取的子串是回文串才能对后面的子串进行递归否则应该是循环遍历直到当前子串是回文串或结束for循环即递归与回溯发生的条件是

组合总和

II中只有满足“当前取的值不重复”的条件才能递归是一样的。

所以也可以写成for(...)

{//