1
# Runtime: 1302 ms (Top 13.95%) | Memory: 35.7 MB (Top 6.05%)
2
"""
3
we can approach this problem using manacher's algorithm with backtracking and recursion
4
"""
5

6

7
class Solution:
8
    def partition(self, s: str) -> List[List[str]]:
9
        lookup = {"": [[]]}
10

11
        def lps(s):
12
            if s in lookup:
13
                return lookup[s]
14

15
            final_res = []
16
            result_set = set()
17
            for k in range(len(s)):
18
                i, j = k, k
19

20
                # check for odd length palindromes
21
                while i >= 0 and j < len(s) and s[i] == s[j]:
22
                    # palindrome found
23
                    res = []
24
                    for partition in lps(s[:i]):
25
                        res.append(partition + [s[i : j + 1]])
26
                    for partition in res:
27
                        for part in lps(s[j + 1 :]):
28
                            temp = partition + part
29
                            if tuple(temp) not in result_set:
30
                                result_set.add(tuple(temp))
31
                                final_res.append(temp)
32
                    i -= 1
33
                    j += 1
34

35
                # check for even length palindromes
36
                i, j = k, k + 1
37
                while i >= 0 and j < len(s) and s[i] == s[j]:
38
                    # palindrome found
39
                    res = []
40
                    for partition in lps(s[:i]):
41
                        res.append(partition + [s[i : j + 1]])
42
                    for partition in res:
43
                        for part in lps(s[j + 1 :]):
44
                            temp = partition + part
45
                            if tuple(temp) not in result_set:
46
                                result_set.add(tuple(temp))
47
                                final_res.append(temp)
48
                    i -= 1
49
                    j += 1
50
            lookup[s] = final_res
51
            return final_res
52

53
        return lps(s)