My accepted Python recursive solution, though not elegent


  • 0
    S
    class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if len(s) == 0:
            return [[]]
        if len(s) ==1:
            return [[s]]
        
        results = []
        #find all candidates of palindromes starting with the 1st letter. 
        candidates = self.generate(s)
        #concatenating each candidate with the following results
        for item in candidates:
            nxt_res = self.partition(s[len(item):])
            for nxt_item in nxt_res:
                if nxt_item:
                    results.append([item] + nxt_item )
                else:
                    results.append([item])
        return results
    
    #generate all the candidates of palindrome starting with the first letter    
    def generate(self, s):
        candidates = []
        for i in xrange(len(s)):
            if s[i] == s[0]:
                if self.check(s[0:i+1]):
                    candidates.append(s[0:i+1])
        return candidates
    
    #check if a string is palindrome
    def check(self,s):
        '''We can also use return s==s[::-1]'''
        if len(s) == 0:
            return False
        first = 0
        last = len(s)-1
        while first <= last:
            if s[first] != s[last]:
                return False
            first += 1
            last -= 1
        return True
    

    The idea is to find all palindrome strings starting with the first letter, then find partitions of the rest of string except for the palindrome substrings. Therefore, it's a combination of recursion and BFS.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.