Palindrome Partitioning

题目

Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return all possible palindrome partitioning ofs.

For example, givens="aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

思路分析

这道题通过题干分析也是用到DFS，我觉得吧这道题做出来之后我才算深刻理解了DFS。

下面的图示可以很好地解释这道题是如何用DFS来实现的

        —————— for loop

| [ ]

| a aa aab

recursive a ab b

| b

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        def dfs(s, length, startIndex, sub, partition, result):
            if sub != sub[::-1]: return
            if length == 0:
                result.append(partition)
                return
            for i in range(startIndex, len(s)):
                dfs(s, length-(i+1-startIndex), i+1, s[startIndex:i+1], partition+[s[startIndex:i+1]], result)
        result = []
        len_s= len(s)
        dfs(s, len_s, 0, '', [], result)
        return result