Amazon VO 面试真题解析：Build Sentences from a String and Word Bank｜DFS / 回溯 / 动态规划

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]:

这道题要求把连续字符串 text 按照 word_bank 中的单词切分成所有可能的合法句子，并保持原始字符顺序不变。核心思路通常是递归回溯结合记忆化搜索：从左到右尝试每个前缀是否在词库中，如果匹配就继续切分剩余部分，把后续结果拼接回来。由于需要返回所有方案，子问题会重复出现，使用缓存可以显著减少重复计算。示例中 "catsandmice" 可以切成 "cats and mice" 和 "cat sand mice" 两种结果，典型地体现了深度优先搜索枚举路径的特点。