LeetCode_Palindrome Partitioning

Posted on | In | Views:

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. 回溯法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    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