0131._palindrome_partitioning.md

131. Palindrome Partitioning

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/palindrome-partitioning/

内容描述

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

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(2^N)******

首先要明确一点，答案是要所有的可能，如果输入为'aabbaa'，那么结果中的["a","a","b","b","aa"]和["aa","b","b","a","a"]是不一样的，都要返回

递归+backtrack

时间复杂度为

Assume isPalindrome as P. Then

T(n) = P(1)+T(n-1)+P(2)+T(n-2)+.....P(n-1)+T(1) + P(n)+T(0)
     = T(n-1)+T(n-2)+...+T(2)+T(1)+T(0) + P(1)+ P(2)+...P(n-1)+P(n)
     
And we know that T(n-1) = T(n-2)+T(n-3)+...+T(2)+T(1)+T(0) + P(1)+ P(2) +...P(n-1)

So T(n) = T(n-1) +T(n-1) + P(n) = 2T(n-1) + P(n)

recursion formula is T(n) = 2T(n-1) + P(n) 
                          = 2T(n-1) + N

上述分析来自ycsust

beats 85.11%

class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.dfs(s, [], res)
        return res
        
    def dfs(self, s, path, res):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.isPalindrome(s[:i]):
                self.dfs(s[i:], path+[s[:i]], res)
                    
    def isPalindrome(self, s):
        return s == s[::-1]