首页 > itarticle > leetcode_palindrome partitioning

leetcode_palindrome partitioning

admin 11月 13, 2020 0

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:

1. 回溯法

下面是一个标准的回溯法的模板：

class :
    def checking(self, string):
        return string[::-1] == string
    
    def back_tracking(self, s, res, start):
        if start == len(s) and len(res) > 0:
            self.results.append(res)
        for i in range(start, len(s)):
            if self.checking(s[start:i+1]):
                self.back_tracking(s, res+[s[start:i+1]], i+1)
                  
    def partition(self, s: str) -> List[List[str]]:
        if not s:
            return []
        
        self.results = []
        self.back_tracking(s, [], 0)
        
        return self.results