Amazon VO 面试真题解析：Word Break II｜动态规划 + DFS 回溯

题目描述

给定一个字符串和一个词典，找出所有把字符串切分成词典单词的方式，返回全部可能的句子，每个分段都必须是词典里的单词。

解题思路

先做一次自右向左的 DP，算出 dp[i] 表示 text[i:] 能否被拆分；再做 DFS 回溯，只有当 dp[j] 为真时才继续递归 text[j:]，剪掉注定无解的分支。这样既保证枚举完整，又避免在无解后缀上反复深挖。

def word_break_ii(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[n] = True
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n + 1):
            if s[i:j] in words and dp[j]:
                dp[i] = True
                break
    res = []

    def dfs(i, path):
        if i == n:
            res.append(" ".join(path))
            return
        for j in range(i + 1, n + 1):
            w = s[i:j]
            if w in words and dp[j]:
                dfs(j, path + [w])

    dfs(0, [])
    return res

复杂度与易错点

最坏情况下答案数量本身是指数级（如 s 全由重复单词组成），DP 只负责剪枝，不改变最坏输出规模。DP 的方向与 DFS 的递归方向要保持一致，都用 dp[j] 判断后缀可行性。

FAQ

为什么先做 DP 再做 DFS，而不是直接 DFS？

直接 DFS 会枚举大量注定无法拼完的分支。DP 提前标出「从某个下标起能否拆完」，DFS 只在可行后缀上继续，显著减少无效递归。

参考来源

• 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辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。