Example 1
ready- Input
s = "leetcode" wordDict = [ "leet", "code" ]- Expected
true- Why
- 'leet' followed by 'code' covers the whole string
Word Break
35 min · wordBreak()mediumOpen in LeetCode #139 ↗
A message can contain only familiar words and still be impossible to split cleanly. One stubborn letter is enough to ruin every proposed reading.
Given a lowercase string s and a list of unique lowercase words wordDict, return
true exactly when all of s can be assembled from dictionary words placed end to
end. This complete split is a segmentation: a sequence of one or more words whose
concatenation equals the original string.
A few ground rules:
- You must cover every character of
s; no gaps or leftovers are allowed. - A dictionary word may be reused as many times as you need.
- You only return whether a segmentation exists, not the words that form it.
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 1_0001 <= wordDict[i].length <= 20sand every dictionary word contain only lowercase English letters.- All words in
wordDictare unique.
Hints
Choose the next cut
Stand at the first uncovered character. Try every later cut whose slice is in the dictionary, then ask the same question from that cut onward.
Remember dead ends
Different choices can bring you to the same character position. Once you know that the suffix starting there can't be segmented, don't solve that suffix again.
Turn the view around
Let dp[i] answer whether the first i characters can be segmented. To prove
dp[i], find an earlier reachable boundary j where s[j:i] is a dictionary word.
Follow-up
How would you return one valid sequence of words instead of only true or false?
Visible cases
Examples
Example 2
ready- Input
s = "applepenapple" wordDict = [ "apple", "pen" ]- Expected
true- Why
- 'apple' can be reused on both sides of 'pen'
Example 3
ready- Input
s = "catsandog" wordDict = [ "cats", "dog", "sand", "and", "cat" ]- Expected
false- Why
- every promising split leaves uncovered characters
Interview signal
Asked at
AmazonGoogleMeta
Memoized recursion — try every next cut
Start at an uncovered position and try every possible next word. A raw recursive search revisits the same suffix through many different cuts. Memoization means caching the answer for each start position, so every suffix is solved once.
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
memo: dict[int, bool] = {}
def can_break(start: int) -> bool:
if start == len(s):
return True
if start in memo:
return memo[start]
for end in range(start + 1, len(s) + 1):
if s[start:end] in words and can_break(end):
memo[start] = True
return True
memo[start] = False
return False
return can_break(0)The base case says that reaching the position just past the final character is a
successful segmentation. Caching failed positions is what tames inputs such as 120
a characters followed by a b: without the cache, the same dead suffix appears in an
exploding number of recursive branches.
Time O(n² · L), where L is the cost of creating and checking a candidate slice.
There are O(n²) possible cuts. Space O(n + d · L) for the recursion, memo, and a
set containing d dictionary words.
Prefix DP — prove reachable boundaries
Dynamic programming (DP) stores answers to overlapping smaller problems and builds
larger answers from them. Here, dp[i] means: the prefix containing the first i
characters can be segmented. The empty prefix is reachable, so dp[0] = True.
For each ending boundary i, inspect every earlier boundary j. If dp[j] is already
true and s[j:i] is a word, then i is reachable too.
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for end in range(1, len(s) + 1):
for start in range(end):
if dp[start] and s[start:end] in words:
dp[end] = True
break
return dp[len(s)]This DP never commits to one early cut. Every reachable boundary stays available to support later prefixes, which is why an attractive dead end can't hide a valid split.
Time O(n² · L) for O(n²) candidate slices and their lookups. Space O(n + d · L) for the DP array and dictionary set.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite