leetcode/131_palindrome_partitioning.py at master · sn1572/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 11 09:10:10 2019

@author: mbolding3
"""


class Solution:


    def findMinimals(self, s):
        # BFS stage, finds indices of all palindromes
        # of length 2 or 3
        len2, len3 = [], []
        N = len(s)
        for i in range(N-1):
            if s[i] == s[i+1]:
                len2.append(i)
            if i <= N-3 and s[i] == s[i+2]:
                len3.append(i+1)
        return(len2, len3)


    def DFS(self, s, index, kind):
        # creates list of all palindrome indices containing
        # the minimal palindrome beginning at index.
        if kind == 2:
            # search for palindromes of the types 'aa...a' or 'baab'
            out = [(index, index+1)]
            left = index
            right = index+1
            while left > 0:
                left -= 1
                if s[left] == s[right]:
                    out.append((left, right))
                else:
                    break
            left = index
            while right < len(s)-1:
                right += 1
                if s[right] == s[left]:
                    out.append((left, right))
                else:
                    break
            right = index+1
        else:
            out = [(index-1, index+1)]
            # search for palindromes of the type 'aba'
            left = index-1; right = index+1

        while left > 0 and right < len(s)-1:
            left -= 1; right += 1
            if s[right] == s[left]:
                out.append((left, right))
            else:
                break

        return(out)


    def generateAllPartitions(self, s):
        len2, len3 = self.findMinimals(s)
        palindromeIndices = dict([])
        for i in len2:
            for a, b in self.DFS(s, i, 2):
                if a in palindromeIndices:
                    palindromeIndices[a].add(b)
                else:
                    palindromeIndices[a] = set([b])
        for i in len3:
            for a, b in self.DFS(s, i, 3):
                if a in palindromeIndices:
                    palindromeIndices[a].add(b)
                else:
                    palindromeIndices[a] = set([b])
        for i in range(len(s)):
            if i in palindromeIndices:
                palindromeIndices[i].add(i)
            else:
                palindromeIndices[i] = set([i])
        # palindromeIndices now contains all the possible palindromes inside s.
        return(palindromeIndices)


    def listPartitions(self, index):
        if index not in self.palindromeIndices:
            return([[]])
        out = []
        for index2 in self.palindromeIndices[index]:
            for array in self.listPartitions(index2+1):
                out.append([self.s[index:index2+1]]+array)
        return(out)


    def partition(self, s):
        self.s = s
        self.palindromeIndices = self.generateAllPartitions(s)
        if len(s) == 1:
            return([[s]])
        elif not s:
            return([])
        return(self.listPartitions(0))


if __name__ == '__main__':
    sol = Solution()
    #test = 'aabaaabaa'
    test = 'aab'
    print(sol.partition(test))