Python recursive Solution.132 ms, 1 line


  • 0
    H

    one line:

    d = {}
    def partition(self, s):
        return ([[s[:i]] + r for i in xrange(1, len(s)) if s[:i] == s[:i][::-1] 
                             for r in self.d.get(s[i:]) or 
                                      self.d.update({s[i:]:self.partition(s[i:])}) or 
                                      self.d[s[i:]]] + (s == s[::-1]) * [[s]])
    #21 / 21 test cases passed.
    #132 ms, beats 96.09% 
    

    equivalent version:

    dic = {}
    def partition(self, s):
        res = (s == s[::-1]) * [[s]]
        for i in xrange(1, len(s)):
            left, right=s[:i], s[i:]
            if left == left[::-1]: #left is a palindrome
                if right not in self.dic:
                    self.dic[right] = self.partition(right)
                for rlist in self.dic[right]:
                    res += [[left] + rlist]
        return res

Log in to reply
 

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