Palindrome Partitioning

Question

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

Return all possible palindrome partitioning of s.

Solution 1:

这道题的特点是求出具体的所有方案，非方案个数，所以不能使用DP，而且求所有的方案个数很容想到使用DFS的方法来实现。

遍历的方法就是前缀或者后缀法，每一次的DFS相当于切到第POS刀，然后只需要判断前缀是否为回文，然后在决定后续的DFS.

解题重点在于要构造出DFS的遍历树：

current = [] 临时遍历变量。

                                      []
                         [u'a']                          [u'aa']
                      [u'a', u'a']                    [u'aa', u'b'] add to result when pos == size of noms
                   [u'a', u'a', u'b'] add to result == size of nums

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def isPalind(self, s):
        start, end = 0, len(s) - 1
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

    def isPalindrome(self, s):
        for i in range(len(s)):
            if s[i] != s[len(s)-1-i]: return False
        return True

    def dfs(self, result, current, s, pos):
        if pos == len(s):
            result.append(list(current))
        for i in range(pos + 1, len(s) + 1):
            prefix = s[pos:i]
            if self.isPalindrome(prefix):
                current.append(prefix)
                self.dfs(result, current, s, i)
                del current[-1]
    def partition(self, s):
        result = []
        self.dfs(result, [], s, 0)
        return result