Fork me on GitHub

Palindrome Partitioning

Posted on

Description

https://leetcode.com/problems/palindrome-partitioning/description/

Solution

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
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ret = []
        st = []
        if s is None or len(s) == 0:
            return []
        self.explore(0, s, st, ret)
        return ret
    
    def valid(self, s, start, end):
        if end == start:
            return True
        middle = (start + end + 1) / 2
        for i in range(start, middle):
            if s[i] != s[start + end - i]:
                return False
        return True
            
        
    def explore(self, start, s, st, ret):
        if start == len(s):
            ret.append(st[:])
            return 
        
        for end in range(start, len(s)):
            if self.valid(s, start, end) is False:
                continue
            st.append(s[start: end + 1])
            self.explore(end + 1, s, st, ret)
            st.pop()
        
        return