Leetcode 131. Palindrome Partitioning

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. 回文如何判断？单独写一个函数判断回文。回文用two pointer即可判断！ 3. 写代码的时候，发现判断substring是否回文时，出现重复计算，这在backtracking很常见！例如： s=”aabab”,计算第一个’b’开始的substring后面是否回文就会计算两次：第一次是判断到[“a”,”a”]后需要判断’b’开始的substring；第二次是判断到[“aa”]后又需要判断。 4. 如何避免重复计算？由于需要知道所有的substring是否回文，那么干脆在backtracking前前把所有的情况一次计算出来，然后保存起来，需要用的时候直接查询即可！问题就变成了：如何快速找到所有的组合? 这个问题的简单粗暴方法：枚举所有的可能substring有o(n^2)种，每一种如果独立计算是否回文，那么每一种的复杂度o(n),总共就是o(n^3)。这种做法，显然没用利用回文的性质：回文的扩展性。例如，”abba”,如果发现”bb”是回文，那么”bb”两边的数如果相等，就可以直接判断”abba”是回文。利用回文的这个性质，减少比较的次数，从而复杂度为o(n^2). 5. 刚才做了一道题，需要把计算所有的组合情况分成一步一步，因为有些步骤不一定需要求；这里，把计算substring的回文情况放在一起计算，是因为分开计算会有大量重复的计算，而且这个题是枚举题，需要枚举所有情况，分开做并不会减少运算量。所以一切的原则，就是怎么省计算次数，怎么做，没有固定的模式和方法！ 5. 这道题的特点就是：dp+backtracking组合。