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. 回文如何判斷？單獨寫一個函數(shù)判斷回文。回文用two pointer即可判斷！ 3. 寫代碼的時候，發(fā)現(xiàn)判斷substring是否回文時，出現(xiàn)重復計算，這在backtracking很常見！例如： s=”aabab”,計算第一個’b’開始的substring后面是否回文就會計算兩次：第一次是判斷到[“a”,”a”]后需要判斷’b’開始的substring；第二次是判斷到[“aa”]后又需要判斷。 4. 如何避免重復計算？由于需要知道所有的substring是否回文，那么干脆在backtracking前前把所有的情況一次計算出來，然后保存起來，需要用的時候直接查詢即可！問題就變成了：如何快速找到所有的組合? 這個問題的簡單粗暴方法：枚舉所有的可能substring有o(n^2)種，每一種如果獨立計算是否回文，那么每一種的復雜度o(n),總共就是o(n^3)。這種做法，顯然沒用利用回文的性質(zhì)：回文的擴展性。例如，”abba”,如果發(fā)現(xiàn)”bb”是回文，那么”bb”兩邊的數(shù)如果相等，就可以直接判斷”abba”是回文。利用回文的這個性質(zhì)，減少比較的次數(shù)，從而復雜度為o(n^2). 5. 剛才做了一道題，需要把計算所有的組合情況分成一步一步，因為有些步驟不一定需要求；這里，把計算substring的回文情況放在一起計算，是因為分開計算會有大量重復的計算，而且這個題是枚舉題，需要枚舉所有情況，分開做并不會減少運算量。所以一切的原則，就是怎么省計算次數(shù)，怎么做，沒有固定的模式和方法！ 5. 這道題的特點就是：dp+backtracking組合。