Python DFS -> DP


  • 1

    DFS 176ms

    class Solution(object):
        def partition(self, s):
            ans = []
            self.helper(s, [], ans)
            return ans
            
        def helper(self, s, temp, ans):
            if not s:
                ans.append(temp)
            for i in range(len(s)):
                if s[:i+1] == s[:i+1][::-1]:
                    self.helper(s[i+1:],temp+[s[:i+1]],ans)
    

    DP 135ms

    class Solution(object):
        def partition(self, s):
            return self.helper(s, {})
            
        def helper(self, s, h):
            if s in h:
                return h[s]
            h[s] = []
            for i in range(len(s)):
                if s[:i+1] == s[:i+1][::-1]:
                    if i+1 == len(s):
                        h[s].append([s])
                    else:
                        for rest in self.helper(s[i+1:], h):
                            h[s].append([s[:i+1]] + rest)
            return h[s]

Log in to reply
 

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