Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”, Return

[ [“aa”,”b”], [“a”,”a”,”b”] ]

s思路： 1. palindrome回文。要列舉所有情況的組合，用backtracking。 2. 回文如何判斷？單獨(dú)寫(xiě)一個(gè)函數(shù)判斷回文?；匚挠胻wo pointer即可判斷！ 3. 寫(xiě)代碼的時(shí)候，發(fā)現(xiàn)判斷substring是否回文時(shí)，出現(xiàn)重復(fù)計(jì)算，這在backtracking很常見(jiàn)！例如： s=”aabab”,計(jì)算第一個(gè)’b’開(kāi)始的substring后面是否回文就會(huì)計(jì)算兩次：第一次是判斷到[“a”,”a”]后需要判斷’b’開(kāi)始的substring；第二次是判斷到[“aa”]后又需要判斷。 4. 如何避免重復(fù)計(jì)算？由于需要知道所有的substring是否回文，那么干脆在backtracking前前把所有的情況一次計(jì)算出來(lái)，然后保存起來(lái)，需要用的時(shí)候直接查詢即可！問(wèn)題就變成了：如何快速找到所有的組合? 這個(gè)問(wèn)題的簡(jiǎn)單粗暴方法：枚舉所有的可能substring有o(n^2)種，每一種如果獨(dú)立計(jì)算是否回文，那么每一種的復(fù)雜度o(n),總共就是o(n^3)。這種做法，顯然沒(méi)用利用回文的性質(zhì)：回文的擴(kuò)展性。例如，”abba”,如果發(fā)現(xiàn)”bb”是回文，那么”bb”兩邊的數(shù)如果相等，就可以直接判斷”abba”是回文。利用回文的這個(gè)性質(zhì)，減少比較的次數(shù)，從而復(fù)雜度為o(n^2). 5. 剛才做了一道題，需要把計(jì)算所有的組合情況分成一步一步，因?yàn)橛行┎襟E不一定需要求；這里，把計(jì)算substring的回文情況放在一起計(jì)算，是因?yàn)榉珠_(kāi)計(jì)算會(huì)有大量重復(fù)的計(jì)算，而且這個(gè)題是枚舉題，需要枚舉所有情況，分開(kāi)做并不會(huì)減少運(yùn)算量。所以一切的原則，就是怎么省計(jì)算次數(shù)，怎么做，沒(méi)有固定的模式和方法！ 5. 這道題的特點(diǎn)就是：dp+backtracking組合。