Python Memoized Solution (Beats 80%)


  • 0
    class Solution(object):
        def partition(self, s):
            memo = dict()
            return self.helper(s, memo)
        
        def helper(self, s, memo):
            if s in memo:
                return memo[s]
            elif not s:
                memo[s] = [[]]
            else:
                temp = []
                for i in range(1, len(s)+1):
                    if self.palindrome(s[:i]):
                        for partition in self.helper(s[i:], memo):
                            temp.append([s[:i]] + partition)
                memo[s] = temp
            return memo[s]
            
        def palindrome(self, s):
            return "".join(reversed(s)) == s
    

Log in to reply
 

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