Skip to content

131 palindrome partitioning

131. Palindrome Partitioning

题目: https://leetcode.com/problems/palindrome-partitioning/

难度: Medium

知道一定是用递归做,但是在怎么拆的部分疑惑了,然后看了hint

key部分长这样,拆法是类似于combination,然后这个len(s) == 0是确保能被拆为palindrome,因为这样剩下的string才是空的

这个recursion tree是这样的,感觉时间复杂度是O(n!),因为每次树都branch n个分支


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


    def dfs(self, s, stringList):
        if len(s) == 0:
            self.res.append(stringList)
        for i in range(1,len(s)+1):
            if self.isPalindrome(s[:i]):
                self.dfs(s[i:],stringList + [s[:i]])

    def isPalindrome(self, s):
        if len(s) <= 1:
            return True
        return s[0] == s[-1] and self.isPalindrome(s[1:-1])

a = Solution()
print a.partition("aab")

# [['a', 'a', 'b'], ['aa', 'b']]

输出是每次必定从单个char的list开始,然后单个char 配 palindrome word,然后palindrome word再来配char...



回到顶部