Given a string text and a list of words word_bank, insert spaces into text to construct all possible sentences where every word is found in word_bank. Return all possible sentences.
Constraints:
- All words in each constructed sentence must exist in
word_bank. - All words in each constructed sentence must preserve the same order as the text.
Example
Input:
text = "catsandmice"
word_bank = ["cat", "cats", "and", "mice", "sand", "ii"]Output:
["cats and mice", "cat sand mice"]def build_sentences(text: str, word_bank: List[str]) -> List[str]:This problem asks you to split a string into all valid sentences using words from a given bank while preserving the original order. A standard solution uses DFS/backtracking with memoization: try every prefix that appears in the word bank, recursively solve the remaining suffix, and combine results into complete sentences. Because the same suffix can be reached multiple times, caching is important to avoid repeated work. The example "catsandmice" produces two valid outputs, which makes this a classic sentence-construction search problem.
