0131. Medium ｜ Palindrome Partitioning.md

• 131 - Palindrome Partitioning
• 难度：Medium｜ 中等
• 相关知识点：String | Dynamic Programming | Backtracking
• 题目链接：https://leetcode.com/problems/palindrome-partitioning/description/

Solution 1 Dynamic Programming

> 从左往右
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPalindrome(sub: str) -> bool:
            return sub == sub[::-1]

        n = len(s)
        dp = [[] for _ in range(n + 1)]
        dp[0] = [[]]

        for i in range(1, n + 1):
            for j in range(0, i):
                sub = s[j:i]
                if isPalindrome(sub) and dp[j]:
                    dp[i] += [_ + [sub]for _ in dp[j]] # _ + [sub]顺序错了也通不过

        return dp[-1]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        dp = [[[]]]
        for i in range(1, len(s) + 1):
            dp.append([])
            for j in range(i):
                tmp = s[j:i]
                if tmp == tmp[::-1]:
                    dp[-1].extend(l + [tmp] for l in dp[j])
        return dp[-1]

i = 3
j 0 -> 2
s[0:3] ❌aab + dp[0] (['']) 
s[1:3] ❌ab + dp[1](['a'])
s[2:3] 'b' + dp[2]([['a', 'a'], ['aa']])

从右往左

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPalindrome(sub: str) -> bool:
            return sub == sub[::-1]

        n = len(s)
        dp = [[] for _ in range(n + 1)]
        dp[n] = [[]]

        for i in range(n-1, -1, -1):
            for j in range(i+1, n+1):
                sub = s[i:j]
                if isPalindrome(sub):
                    dp[i] += [[sub]+ _ for _ in dp[j]] # _ + [sub]顺序错了也通不过
        return dp[0]

Solution 2 Backtracking

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(s):
            return s == s[::-1]
        
        length = len(s)

        def func(index):
            if index >= length:
                res.append(ans[:])
                return
            if index < 0:
                return

            for i in range(index + 1, length + 1):
                string = s[index:i]
                if is_palindrome(string):
                    ans.append(string)
                    func(i) 
                    ans.pop()

        res = []
        ans = []
        func(0)
        return res