LeetCode 140 Word Break II - Implementation

Backtracking with memoization. Build sentences recursively.

def wordBreak(s, wordDict): wordSet = set(wordDict) memo = {}

def backtrack(start):
    if start in memo:
        return memo[start]
    if start == len(s):
        return [""]

    results = []
    for end in range(start + 1, len(s) + 1):
        word = s[start:end]
        if word in wordSet:
            for sentence in backtrack(end):
                if sentence:
                    results.append(word + " " + sentence)
                else:
                    results.append(word)

    memo[start] = results
    return results

return backtrack(0)

$O(2^n \cdot n)$ worst case. $O(n \cdot 2^n)$ space.