140. Word Break II

Problem¶

Insert spaces into s so every segment is in wordDict; return every valid sentence, and allow words to be reused.

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
output = ["cat sand dog", "cats and dog"]

Key trick¶

Memoize all valid decompositions of each suffix index; the empty suffix has one decomposition, the empty sequence of words.

Trap¶

Forgetting the empty base decomposition prevents the first word from being added.
Backtracking without memoization repeatedly solves the same suffix.
Returning a string instead of a list of sentences.
Assuming the number of answers is polynomial; enumeration can be exponential.

Why is it interesting?¶

It combines dynamic programming with output generation: feasibility alone is easy, but every valid path must also be reconstructed.

Python solution¶

from functools import cache


class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
        words = set(wordDict)
        n = len(s)
        lengths = {len(word) for word in words}

        @cache
        def dfs(i):
            # One empty decomposition completes a sentence.
            if i == n:
                return [()]

            res = []

            for length in lengths:
                j = i + length
                if j <= n:
                    word = s[i:j]
                    if word in words:
                        # Prepend this word to every decomposition of the suffix.
                        for suffix in dfs(j):
                            res.append((word, *suffix))

            return res

        return [" ".join(parts) for parts in dfs(0)]

Time: \(O(n2^n)\) in the worst case, including construction of all answers.
Space: \(O(n2^n)\) for memoized decompositions and returned answers.

Comment on my solution¶

The dynamic programming direction is reasonable, but several indexing and type errors prevent it from working:

A prefix DP is simpler with n + 1 states and dp[0] initialized with one empty decomposition.
k is a zero-based bucket index, so the corresponding word length is k + 1.
The condition j > 0 excludes words beginning at index zero.
The slice has the wrong endpoint because k is not the word length.
s[...] is compared with words_k, which is a list rather than one word.
word_k is undefined; the loop variable is word.
Assigning to dp[i] overwrites sentences found through earlier matches.
" ".join(dp[-1]) cannot join lists of words and returns one string rather than a list of sentences.

# WRONG
# I think the logic is correct but the indices are wrong
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
        # "catsanddog", ["cat","cats","and","sand","dog"]
        # -> ["cats and dog","cat sand dog"]
        # "catsandog", ["cat","cats","and","sand","dog"]
        # -> []


        n = len(s)
        # dp[i] = list of all possible word combination whose concatenation
        #         matches s[:i+1]
        dp = [[] for _ in range(n)]
        max_word_len = max(len(word) for word in set(wordDict))
        words = [[] for _ in range(max_word_len)]
        for word in set(wordDict):
            words[len(word) - 1].append(word)

        for i in range(n):
            for k, words_k in enumerate(words):
                for word in words_k:
                    j = i - k
                    if j > 0 and s[j:j + k] == words_k:
                        dp[i] = [prev + [word_k] for prev in dp[j]]
        return " ".join(dp[-1])