動機

感覺回文的DP就是判斷是不是回文ㄟ

Problem

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 = aabOutput: [[a,a,b],[aa,b]]

Example 2:

Input: s = aOutput: [[a]]

 

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

Sol

用DP做回文判斷的方式，之後就是backtracking一路列舉下去

class Solution:
    @functools.cache
    def isPalin(self,i,j):
        if j-i < 0:
            return False
        elif j-i == 1 or j-i == 0:
            return True
        else:
            return (self.s[i] == self.s[j-1]) and self.isPalin(i+1,j-1)
    def dfs(self,i,acc=[]):
        #print(self.s[i:j],self.isPalin(i,j))
        if i >= len(self.s):
            return [acc]
        else:
            ret = []
            for k in range(i+1,len(self.s)+1):
                #print(self.s[i:k],self.isPalin(i,k),self.s[k:j],self.isPalin(k,j))
                if self.isPalin(i,k):
                    ret += self.dfs(k,acc+[self.s[i:k]])
            #print(i,j,ret)
            return ret
    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        return self.dfs(0)