###### tags: `Leetcode` `medium` `dynamic programming` `backtracking` `python` `Top 100 Liked Questions`

# 131. Palindrome Partitioning

## [題目連結:] 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.

A **palindrome** string is a string that reads the same backward as forward.

**Example 1:**

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

**Example 2:**

Input: s = "a"
Output: [["a"]]

## 解題想法:
* 題目為求:找出字串中，所有可以構成回文的子字串
* Sol1: 使用遞迴
* Sol2: 使用DP

## Python: Sol1_dfs
* 每個位置為起始，遞迴求是否能成為回文

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        self.res=[]
        self.dfs(s,0,[])
        return self.res
    def dfs(self,s,start,path):
        if start>len(s)-1:
            self.res.append(path)
            return 
        for pos in range(start,len(s)):
            #子字串為start~pos
            if self.palindrome(s[start:pos+1]):
                #此sub自己為一段，dfs跑pos+1~end
                self.dfs(s,pos+1,path+[s[start:pos+1]])
        
    #判斷遞迴
    def palindrome(self,s):
        if not s:
            return True
        head=0
        tail=len(s)-1
        while head<=tail:
            if s[head]!=s[tail]:
                return False
            head+=1
            tail-=1
        return True

result = Solution()
s = "abbab"
ans = result.partition(s)
print(ans)

## Python: Sol2_dp
* 定義dp[i]: 存的為s[0:i]的所有回文分割串

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        #dp[i]存的為s[0:i]的所有回文分割串
        dp = [ [] for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            #遍歷0~i-1之間每個位置j 
            for j in range(i):
                #若s[j:i]為回文 
                if self.palindrome(s[j:i]):
                    if len(dp[j])>0:
                        #把dp[j]儲存的所有分割與s[j:i]連線並append到dp[i]中
                        for path in dp[j]:
                            dp[i].append(path+[s[j:i]])
                    else:
                        dp[i].append([s[j:i]])
        return dp[-1]
    
    def palindrome(self,s):
        if not s:
            return True
        head=0
        tail=len(s)-1
        while head<=tail:
            if s[head]!=s[tail]:
                return False
            head+=1
            tail-=1
        return True

result = Solution()
s = "aab"
ans = result.partition(s)
print(ans)