Palindrome Partitioning

LeetCode 131

Although this is similar to Longest Palindromic Substring, yet the idea is similar to Word Break 2. We use backtracking at each place it could be partitioned.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        results: List[List[str]] = []
        def search(i, path: List[str]):
            if i == n: results.append(path)
            
            for j in range(i, n):
                sub = s[i:j+1]
                if sub == sub[::-1]:
                    search(j+1, path+[sub])
        search(0, [])
        return results