如果死套以前backtrack的公式这题会死的很惨,因为这个不是求组合而是求substring。也就是长度可以为1,为2,为...
最好画图看:
尽管这题和All possible palindrome 很像, 但是很不一样!我们这里backtrack的for loop意思是:
假设从第i个起点开始当substring的头,能够产生的所有substring为 什么。
比如以0为起点,可以产出,a,aa,aab.
如果以1位起点,可以产出 aa, ab
如果以b为起点,也就b自己一个。
backtrack语句放在for Loop外面也是一个非常容易错的点。放在外面的原因是backtrack会调整substring的起始点位置+1. 我们得等这一轮起始点的弄完,才可以去考率下一轮的。
我这个算法过了99%的test,但是还是memory 爆炸了最后。
Best:
哎呀 卧槽。。。突然发现这题怎么感觉和之前那个longest palindromic substrings一样。。。
哦 不对 不一样。。。因为这题在左右延长的时候,每一步基本都要算一次palidrome.
my own ways:
哈哈 其实还是差不多