What is the main pattern to solve Word Break efficiently?

The problem relies on array scanning combined with hash lookups to verify dictionary words. DP or memoization prevents redundant substring checks and handles repeated word reuse.

Can I use recursion instead of iterative DP for Word Break?

Yes, recursion with memoization works by caching results for each start index, avoiding redundant computations while still checking all substring splits efficiently.

How does a trie improve Word Break performance?

A trie allows prefix-based early termination, reducing unnecessary substring scans. It works well with DP or memoization to efficiently track valid segmentations with multiple dictionary words.

What common mistakes lead to timeouts in Word Break?

Inefficiently checking all substrings without DP or memoization, repeatedly scanning the wordDict without hash lookups, and ignoring repeated word usage can cause significant slowdowns.

Are there follow-up variants of Word Break to practice?

Yes, including Word Break II to return all segmentations, limited reuse versions where each word has usage limits, and counting valid segmentations instead of boolean output.

#139

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。示例 1：输入: s = "leetcode", wordDict = ["leet"…

数组哈希表字符串动态规划字典树

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

lightbulb

解题思路

方法一：哈希表 + 动态规划

我们定义 $f[i]$ 表示字符串 $s$ 的前 $i$ 个字符能否拆分成 $wordDict$ 中的单词，初始时 $f[0]=true$ ，其余为 $false$ 。答案为 $f[n]$ 。

考虑 $f[i]$ ，如果存在 $j \in [0, i)$ 使得 $f[j] \land s[j:i] \in wordDict$ ，则 $f[i]=true$ 。为了优化效率，我们可以使用哈希表存储 $wordDict$ 中的单词，这样可以快速判断 $s[j:i]$ 是否在 $wordDict$ 中。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            f[i] = any(f[j] and s[j:i] in words for j in range(i))
        return f[n]

speed

复杂度分析

指标	值
时间	O(n^3 + m \cdot k)
空间	O(n + m \cdot k)

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize the overlapping subproblem structure in this string segmentation scenario?
question_mark
Can you optimize substring lookups to avoid repeated dictionary searches using hash sets or tries?
question_mark
Will you explain how DP or memoization prevents redundant scanning of overlapping string segments?

warning

常见陷阱

外企场景

error
Forgetting that dictionary words can be reused multiple times, leading to false negatives in segmentation.
error
Checking all substrings inefficiently without leveraging DP or memoization, causing timeouts.
error
Using a list search instead of a hash set, which increases lookup time from O(1) to O(m) per substring.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Word Break II: Return all possible segmentations of s instead of a boolean, exploring recursion with memoization.
arrow_right_alt
Word Break with Limited Reuse: Each word can be used only a fixed number of times, requiring additional tracking per word.
arrow_right_alt
Word Break III: Count the number of valid segmentations instead of returning a boolean, focusing on DP sum accumulation.

help

常见问题

外企场景

继续练习

#140 单词拆分 II #691 贴纸拼词 #792 匹配子序列的单词数