give a string and a dictionary of words, find all ways to break string into valid words

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

Output:
[
  "cat sand dog",
  "cats and dog"
]

给一个字符串 s 和一个单词字典 wordDict，要求找出所有合法拆分方式。

每个拆出来的单词都必须在字典里。

比如：

catsanddog

可以拆成：

cat sand dog
cats and dog

所以要返回所有结果，而不是只判断能不能拆。

用 DFS 从字符串开头开始尝试切分。

每次枚举一个前缀，如果这个前缀在字典里，就继续递归处理剩下的字符串。

比如 catsanddog：

cat + sanddog
cats + anddog

两条路径都能继续拆完，所以都加入答案。

为了避免重复计算同一个后缀，可以加 memo：

memo[index] = 从 index 开始能拆出的所有句子

这样同一个位置只计算一次。

如果你也在准备 Amazon Front-End 或其他北美大厂面试，csoahelp 可以提供一对一面试辅助服务。我们会根据你的目标岗位，整理高频真题、讲解解题思路、模拟真实面试流程，并帮助你优化表达方式。无论是算法题、前端系统设计，还是 behavioral question，都可以针对性练习，减少盲目刷题，提高面试通过率。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~