Word Break II - Video Solutions

Problem Overview: Given a string s and a dictionary of valid words, return all possible sentences formed by inserting spaces in s so every segment exists in the dictionary. Unlike Word Break I, this problem requires generating every valid sentence rather than just checking feasibility.

Approach 1: Backtracking with Memoization (Time: O(n * 2^n), Space: O(n * 2^n))

This approach explores every possible prefix of the string and recursively builds sentences from the remaining suffix. For each index, iterate through the string and check whether s[i:j] exists in a hash set built from the dictionary. If it does, recursively solve the suffix starting at j. Memoization stores results for previously computed indices so the same substring is never recomputed. Without memoization the recursion tree explodes; caching reduces repeated work significantly. The recursion essentially builds a tree of sentence combinations where each node represents a valid dictionary split. This technique heavily uses backtracking and memoization to efficiently enumerate all possibilities.

Approach 2: Dynamic Programming with Sentence Reconstruction (Time: O(n^2 + n * 2^n), Space: O(n * 2^n))

Dynamic programming first determines which prefixes of the string can form valid segmentations. Create a DP array where dp[i] stores all sentences that can construct the substring s[0:i]. Iterate through indices and check each previous position j. If s[j:i] is a dictionary word and dp[j] already contains valid sentences, append the new word to those sentences. This gradually builds complete results for dp[n]. The dictionary lookup runs in constant time using a hash set, making substring validation efficient. This technique leverages dynamic programming on top of standard string manipulation.

Approach 3: Trie Optimized Search (Time: O(n * 2^n), Space: O(n * 2^n + dict))

Instead of repeatedly checking substrings against a hash set, you can store the dictionary in a Trie. Starting from index i, walk the Trie while scanning characters in the string. Each time you hit a terminal node, you found a valid word and recursively process the remainder. Trie traversal avoids repeated substring allocations and speeds up dictionary checks when the word list is large. This approach pairs naturally with recursion and memoization while reducing lookup overhead using a Trie.

Recommended for interviews: Backtracking with memoization is the most common solution expected by interviewers. It clearly demonstrates recursive decomposition and caching to control exponential branching. Dynamic programming is also strong if you prefer bottom‑up reasoning. A naive brute force recursion without memoization proves the idea but performs poorly on longer inputs, so the optimized memoized version usually signals stronger problem‑solving ability.