*Simple* 104ms Python accepted answer

  • 1

    Below is my solution. The detail view tells me it's within the fastest in python. It is really easy to understand. I basically go through an existing partition, index by index, and each time I find a new palindrome, I branch out with the new partition and go on. It's of course a recursive solution (Depth-First). Comments are in the code.

    def partitionRec(p, index, ps):
        # If we're at the last position of the current partition, add the partition and leave.
        if index == len(p)-1:
            ps += [p]
        # Tries to create a palindrome at "index"
        if p[index] == p[index+1]: # first way 'ab', 'ba'
            pi = p[:]
            pi[index] = pi[index] + pi[index+1]
            del pi[index+1]
            partitionRec(pi, index, ps) #go look for other partitions based on the new one
        if index > 0 and p[index-1]==p[index+1]: # second way 'ab', 'c', 'ba'
            pii = p[:]
            pii[index-1] = pii[index-1] + pii[index] + pii[index+1]
            del pii[index+1]
            del pii[index]
            partitionRec(pii, index - 1, ps) #go look for other partitions based on the new one
        # Go forward on the ame partition
        partitionRec(p, index+1, ps)
    def partition(s):
        p = [c for c in s] #initialize the first partition
        ps = [] #initialize list of partitions
        partitionRec(p,0,ps) #go!
        return ps
    class Solution:
        # @param s, a string
        # @return a list of lists of string
        def partition(self, s):
            return partition(s)

    The only tricky part is to understand why we have all the palindrome partitions this way, even while not going back when we have a new partition. It comes from the properties of a palindrome, which can always be grown from its middle (second case in the code) or left to right.


Log in to reply

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