dp(with memo) beats 98% python solution


  • 0
    class Solution(object):
        def partition_core(self, s):
            s_len = len(s)
            if self.memo[s_len]:
                return self.memo[s_len]
            res = []
            for i in range(len(s)-1, -1, -1):
                current = s[i:]
                if current==current[::-1]:
                    pre_res = self.partition_core(s[:i])
                    res += [r+[current] for r in pre_res]
            self.memo[s_len] = res
            return res
    
        def partition(self, s):
            self.memo = [None]*(len(s)+1)
            self.memo[0]=[[]]
            return self.partition_core(s)
    

    keypoints:

    1. cut s into two part (from backend to start), if backend is Palindrome then solve the sub problem of prefix
    2. use a memo to avoid the repeated calling.

Log in to reply
 

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