Startup VO 面试真题解析：Word Break Sentence Generation with Glossary Entries

题目描述

给定一个文本字符串和一个词表，插入空格生成所有可能的句子，要求每一个分段都恰好匹配词表里的一个条目。Part 2 通常要求同时考虑输入与输出，返回全部合法句子。

解题思路

用带备忘录的 DFS 枚举切分位置：从当前下标 i 出发，尝试所有结束位置 j，若 text[i:j] 是词表条目，则递归求解 text[j:] 的所有句子并拼接。备忘录避免对同一后缀重复枚举。

def word_break_sentences(text, glossary):
    words = set(glossary)
    n = len(text)
    memo = {}

    def dfs(i):
        if i == n:
            return [""]
        if i in memo:
            return memo[i]
        res = []
        for j in range(i + 1, n + 1):
            w = text[i:j]
            if w in words:
                for tail in dfs(j):
                    res.append(w if not tail else w + " " + tail)
        memo[i] = res
        return res

    return dfs(0)

复杂度与易错点

最坏情况下所有切分都是答案，输出本身可能是 O(2^n) 个句子；备忘录只去除重复子问题，不改变最坏输出规模。词表规模大时，应先预处理前缀或最大词长，避免对每个 j 都切片判断。

FAQ

为什么 DFS 里要先查 memo 再枚举？

同一后缀可能从多个前缀到达，备忘录把「从 i 到结尾的所有句子」缓存下来，避免重复枚举同一子问题。

参考来源

• LeetCode 139 — Word Break
• LeetCode 140 — Word Break II

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。