Google — Word Break II (DP + Backtracking with Memoization)

Problem Statement#

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist only of lowercase English letters
• All wordDict entries are unique

Input:  s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Input:  s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Why This Problem Matters#

Word Break II (LeetCode 140) is a Google onsite favorite that tests both dynamic programming feasibility checking and backtracking enumeration. Google's search engine, natural language processing pipelines, and query segmentation tools all use word segmentation algorithms — the exact computation this problem models. Understanding when to memoize recursive calls is what separates an O(N * 2^N) solution from an efficient one.

The naive recursive solution without memoization revisits the same substrings repeatedly. For example, if s[5:] appears in multiple valid segmentations, without memoization it would be re-explored from scratch each time. Memoizing the set of sentences that can be formed from each suffix reduces redundant work dramatically.

Amazon and Microsoft also ask this problem. Word Break I (LeetCode 139, just checking feasibility) is asked far more often and should be mastered first; Word Break II is the harder extension requiring actual path reconstruction.

The Core Insight#

Use memoized backtracking. Define dp(start) as the list of all valid sentences that can be formed from s[start:]. At each position, try every possible word from the dictionary. If s[start:start+len(word)] == word, recursively get all sentences from dp(start+len(word)), prepend word, and collect results.

Memoize dp(start) so each suffix is processed at most once. The total time is O(N * 2^N) in the worst case (exponential number of sentences), but memoization avoids re-computing the same subproblem.

Optionally, first run Word Break I (feasibility DP) to prune the search early if no valid segmentation exists.

Visual Dry Run#

s = "catsanddog", wordDict = {cat, cats, and, sand, dog}

Solution (Optimal)#

from functools import lru_cache
 
class Solution:
    def wordBreak(self, s: str, wordDict: list) -> list:
        word_set = set(wordDict)
 
        @lru_cache(maxsize=None)
        def dp(start):
            if start == len(s):
                return [""]
            sentences = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in word_set:
                    for suffix_sentence in dp(end):
                        if suffix_sentence:
                            sentences.append(word + " " + suffix_sentence)
                        else:
                            sentences.append(word)
            return sentences
 
        return dp(0)

var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();
 
    function dp(start) {
        if (memo.has(start)) return memo.get(start);
        if (start === s.length) return [""];
 
        const sentences = [];
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.slice(start, end);
            if (wordSet.has(word)) {
                const suffixes = dp(end);
                for (const suffix of suffixes) {
                    sentences.push(suffix ? word + " " + suffix : word);
                }
            }
        }
 
        memo.set(start, sentences);
        return sentences;
    }
 
    return dp(0);
};

Time: O(N * 2^N * N) worst case — 2^N sentences, each up to N characters long; memoization avoids recomputing subproblems Space: O(N * 2^N) — memoized results store all sentences for each suffix

Common Mistakes#

• Not memoizing — exponential recomputation of shared suffixes
• Returning a reference to a mutable list from the cache — subsequent calls modify cached results
• Building sentences by appending space at the end — trailing space in output
• Not handling the base case: when start == len(s), return [""] (list with one empty string)
• Confusing Word Break I (boolean feasibility) with Word Break II (enumerate all sentences)

Interview Tips#

• Start by solving Word Break I (feasibility) before Word Break II — shows structured escalation
• Explain memoization clearly: "Without memo, dp(5) is computed every time any prefix leads to position 5"
• Use @lru_cache in Python for clean memoization; use a Map in JavaScript
• The base case returning [""] (not []) is the key — it allows the sentence to terminate cleanly
• Mention that worst-case is exponential (e.g., "aaa...a" with dictionary ["a","aa","aaa"]) — exponential sentences

Follow-up Questions#

• How do you check if any segmentation is possible (Word Break I)? — DP array: dp[i] = any(dp[j] and s[j:i] in dict for j < i)
• How do you find the segmentation with the fewest words? — BFS from index 0, level = number of words
• What if the string is very long (1000+ chars)? — Word Break I with DP first to prune; backtracking may still be exponential
• How would you use a Trie instead of a set? — Build a Trie from wordDict; use it for prefix matching during the scan
• What if the dictionary can contain duplicates? — Deduplicate first; no effect on correctness

Key Takeaways#

• Word Break II requires enumeration of all valid segmentations — use memoized backtracking
• The base case dp(len(s)) = [""] allows clean sentence construction by prepending words with spaces
• Memoize on the start index: dp(start) returns all valid sentences from s[start:]
• Without memoization, time is O(N * 2^N) recursive calls per suffix — with memo, each suffix is solved once
• Google tests this to verify understanding of recursive search, NLP segmentation, and memoization correctness
• Always run Word Break I feasibility check first in production — avoids full backtracking on impossible inputs
• A Trie-based word lookup allows early termination of invalid prefixes, improving average-case performance