[LeetCode]Palindrome Partition

Backtrack的题型。相对于每次递归用O(n)的时间来判断当前substring是否为palindrome，我们可以对string做预处理，生产一个map来表示substr(i, j)是否是palindrome，这样的话O(1)时间即可判断。空间复杂度O(n^2)，因为要存bool来表示任意substring是否为palindrome。时间复杂度worst caseO(2^(n - 1))，因为最坏情况在每一处我们都要考虑切割与不切割的情况，比如，"aaaa.....aa"，但是一般情况而言，我们的剪枝会有效的减小时间复杂度，代码如下：