Palindrome Partitioning

可以说这个系列的两道题已经基本上揭示了回溯以及DFS和动态规划之间的深刻联系，这里的第一题需要求出所有对称字符串的划分方案，这样看的话这道题的思路也就是一般的回溯法而已，然后每次我们需要对start到i之间的字符串是否对称进行一个检查，如果不对称我们就需要跳过此种选择方案，下面是代码

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        tmp, res = [], []
        self.helper(s, 0, len(s), tmp, res)
        return res

    def helper(self, string, start, end, tmp, res):
        if start >= end:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(start, end):
            if not self.isPalin(string, start, i):
                continue
            tmp.append(string[start : i + 1])
            self.helper(string, i + 1, end, tmp, res)
            tmp.pop()

    def isPalin(self, string, start, end):
        while start < end:
            if string[start] != string[end]:
                return False
            start += 1
            end -= 1
        return True

这里需要明确一点，即能用回溯来做的题，本质上也是可以用DP来做的，但是因为DP只能记录方案数或者对输入判定yes或者no，在回溯求所有可行方法时，DP只能拿来当一个辅助道具了，然而他们两者在做的事本质上是一样的，所以这里我们可以建立一个DP矩阵来省去对于对称与否的这个极其浪费时间的函数，另外这里的dp矩阵是终点在前起点在后，因为我们使用的是矩阵的左下部分

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        n = len(s)
        dp = [[False] * n for _ in xrange(n)]

        for i in xrange(n):
            for j in xrange(i + 1):
                if i == j:
                    dp[i][j] = True
                elif i - 1 == j:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = ((s[i] == s[j]) and dp[i - 1][j + 1])

        tmp, res = [], []
        self.helper(s, 0, n, tmp, res, dp)
        return res

    def helper(self, string, start, end, tmp, res, ref):
        if start >= end:
            res.append(tmp[:])
            return 

        for i in xrange(start, end):
            if ref[i][start]:
                tmp.append(string[start : i + 1])
                self.helper(string, i + 1, end, tmp, res, ref)
                tmp.pop()