这是一道 TikTok 面试中出现的字符串题。第一眼看起来是比较经典的 Word Break II，但真正值得注意的是 Part 2：输入字符串和词典中的词本身都可能包含空格。如果仍然按照普通的单词拆分思路处理，很容易在 follow-up 中出错。

Given a text string and a glossary, insert spaces to generate all possible sentences where every segment matches a glossary entry.
In Part 2, both the input text and glossary entries may already contain spaces, which must also be handled correctly.

给定一个字符串 text 和一个词典 glossary，需要在字符串中插入空格，使拆分后的每一部分都能够在 glossary 中找到，并返回所有合法的拆分结果。

例如：

text = "catsanddog"

glossary = ["cat", "cats", "and", "sand", "dog"]

可以得到：

"cats and dog"

"cat sand dog"

题目的 Part 2 又增加了一个比较关键的条件：

text 本身可能已经包含空格，glossary 中的词条也可能包含空格。

例如词典中可能直接存在：

"new york"

这意味着不能简单地先按照空格拆分输入，也不能为了方便直接删除或 normalize 原字符串中的空格。

核心仍然可以从字符串当前位置开始，尝试寻找所有能够匹配 glossary 的词条。

假设当前处理到位置 i，就检查从这里开始的哪些 substring 可以完整匹配一个 glossary entry。匹配成功后，继续处理剩余部分。

如果最终走到了字符串结尾，就得到了一种合法拆分。

这种题如果直接 DFS，会反复计算相同的 suffix。例如多个不同的前缀拆分可能最终到达同一个字符串位置，所以通常会配合 memoization，记录“从位置 i 开始能够产生哪些合法结果”。

因此整体思路可以理解为：

DFS / Backtracking + Memoization

相比直接暴力枚举所有插空格的位置，这种方式更容易解释，也更符合面试中的预期。

普通 Word Break 往往默认：

字符串中没有空格，dictionary 中每个 entry 也是单独的单词。

但这道题明确说明 glossary entry 可能本身就是一个带空格的 phrase。

例如：

"new york"

这里中间的空格属于 glossary entry 本身，并不是我们为了划分答案而额外插入的 separator。

因此实现时最好不要把结果一直当成一个字符串拼接，而是保存：

["I", "love", "new york"]

这样的 glossary entry 序列。

等找到完整答案以后，再统一把这些 entry 用空格连接起来。

这样 "new york" 内部原有的空格会被完整保留，同时也不会和算法额外添加的分隔空格混在一起。

同样，匹配 substring 时也应该直接基于 原始 text 的字符位置进行匹配，而不是先对 text 做 split(" ")。这样无论 text 或 glossary 中是否已经存在空格，都可以使用同一套递归逻辑。

这道题本身并不算特别难，难点更多在于候选人是否能及时发现边界条件。

追问：

如果 glossary 中存在多个不同长度的匹配怎么办？

如果同一个 suffix 被大量重复计算怎么办？

如果 glossary entry 自己包含空格怎么办？

输入中原本存在的空格和我们插入的空格应该如何区分？

如果答案数量本身非常多，复杂度会怎样？

其中最后一点也很重要。这类题即使使用 memoization，也无法保证最终复杂度是多项式，因为题目要求返回所有结果。如果合法拆分本身就有指数级数量，那么仅仅生成这些答案就已经需要指数级时间。

所以面试中没有必要过度纠结一个非常漂亮的 Big-O，更重要的是说明：

memoization 可以避免重复计算相同 suffix，但无法避免输出结果本身带来的成本。

csoahelp 实时面试辅助

这类题也是我们在实时面试辅助中比较典型的场景。

很多候选人并不是完全不会做 Word Break，而是在面试官突然增加 Part 2、修改输入条件或者加入新的 edge case 后，没有足够时间重新整理思路。

我们的实时文本辅助会根据面试官最新给出的条件，快速帮助候选人识别题型、整理当前可行方案，并提示类似 memoization、重复 suffix、带空格 glossary entry、边界条件 这样的关键点，让候选人能够继续用自己的语言完成分析和实现，而不是在 follow-up 阶段卡住。

如果面试前希望针对 TikTok、Google、Meta、Amazon、Stripe 等公司的 Coding Interview 做准备，也可以通过 Mock Interview 提前练习这种“基础题 + 连续 follow-up”的面试节奏。实际面试中，很多题真正拉开差距的，恰恰不是第一问，而是后面不断变化的条件。

csoahelp 提供海外科技公司面试的实时文本辅助和 Mock 面试服务，可针对 Stripe、Google、Amazon、OpenAI 等公司的 Coding、System Design 和 Behavioral Interview 进行模拟与复盘。

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