Word Break II

Word Break II

What is this problem about?

Building upon "Word Break," this version asks you to return all possible sentences that can be formed by adding spaces in the string s such that each word is a valid dictionary word.

Why is this asked in interviews?

This "Hard" problem is popular at Uber and Microsoft. It combines Dynamic Programming (to check for feasibility) with Backtracking (to reconstruct the paths). It tests a candidate's ability to manage complex return types (lists of strings) and efficient memory usage via memoization.

Algorithmic pattern used

The pattern is Backtracking with Memoization. You define a function that returns all possible sentence completions for a given suffix of the string.

1. For the current string, iterate through all possible prefixes.
2. If a prefix is in the dictionary, recursively call the function for the remaining suffix.
3. Combine the prefix with all results from the recursive call.
4. Store the results in a map (memo) to avoid re-solving the same suffix.

Example explanation

String: catsanddog, Dictionary: ["cat", "cats", "and", "sand", "dog"].

1. cat + sanddog -> cat + sand + dog -> "cat sand dog"
2. cats + anddog -> cats + and + dog -> "cats and dog" Result: ["cat sand dog", "cats and dog"].

Common mistakes candidates make

• Memory Limit Exceeded: Not using memoization, or storing too many intermediate strings in a very large input.
• No Early Exit: Not checking if a word break is even possible before trying to generate all sentences. You can run the "Word Break I" DP first to save time.
• String Concatenation in Loops: Creating too many intermediate string objects (use a list and join if performance is critical).

Interview preparation tip

Understand that while DP tells you if a solution exists, Backtracking allows you to find the solution. Combining them is a common pattern for "Return all possible..." type questions.