Python DP 39ms (99.75%)


  • 1

    DP. Memoize combinations at each index as duplicated work results from each index being potentially approachable by a variety combinations.

        def wordBreak(self, s, wordDict):
    
            def breaker(i, s, W, L, memo):
                if i not in memo:
                    for l in L:
                        if i + l <= len(s):
                            w = s[i:i+l]
                            if w in W:
                                if i+l == len(s):
                                    memo[i].append(w)
                                else:
                                    b = breaker(i+l, s, W, L, memo)
                                    if b:
                                        memo[i] += [' '.join([w, sub]) for sub in b]
                return memo[i]
            
            memo = collections.defaultdict(list)
            breaker(0, s, set(wordDict), set(len(w) for w in wordDict), memo)
            return memo.get(0, [])
    

Log in to reply
 

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