Word Break
The fundamental string segmentation problem that powers spell checkers, search engines, and tokenizers.
TL;DR
Use DP where dp[i] is true if s[0:i] can be segmented into dictionary words. For each position, check all valid last-word boundaries. Runs in O(N squared) substring checks with O(N) space. Optimize with a Trie for prefix-based dictionary lookup or bound the inner loop by maximum word length. This is the algorithmic foundation of NLP tokenization and extends the state-transition pattern from Decode Ways.
Problem
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Intuition
Imagine you are building a search engine. A user types “newyorktimes”. Your system needs to understand that this is likely “new york times”. This process of breaking a continuous stream of characters into meaningful units is called Segmentation or Tokenization.
The “Word Break” problem is the algorithmic core of this task. At every character, we have a choice: “Do I end the current word here?”
If we split “newyorktimes” at index 3 (“new”), we are left with the subproblem of segmenting “yorktimes”. If we split at index 7 (“newyork”), we are left with “times”.
This overlapping subproblem structure screams Dynamic Programming.
Approach 1: Brute Force Recursion
Let canBreak(start_index) be a function that returns true if the suffix s[start_index:] can be segmented.
Algorithm:
- Iterate through every possible end index
endfromstart + 1tolength. - Check if the substring
s[start:end]is in the dictionary. - If it is, recursively call
canBreak(end). - If the recursive call returns
true, then the whole string is valid. Returntrue.
from typing import List
def wordBreak_recursive(s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict) # O(1) lookup
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set and can_break(end):
return True
return False
return can_break(0)
Complexity:
- Time: O(2^N). In the worst case (e.g.,
s = "aaaaab",dict = ["a", "aa", "aaa"]), no segmentation works and we explore every possible partition before giving up. - Space: O(N) for recursion depth.
Approach 2: Recursion with Memoization
We are re-calculating the same suffixes. can_break(5) might be called multiple times. Let’s cache it.
def wordBreak_memo(s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict)
memo = {}
def can_break(start):
if start in memo:
return memo[start]
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set and can_break(end):
memo[start] = True
return True
memo[start] = False
return False
return can_break(0)
Complexity:
- Time: O(N^3). There are N states. For each state, we iterate N times. String slicing/hashing takes O(N). Total N × N × N.
- Space: O(N) for memoization.
Approach 3: Iterative Dynamic Programming
Let dp[i] be true if the prefix s[0...i-1] (length i) can be segmented.
Initialization:
dp[0] = true(Empty string is valid).
Transitions:
For each i from 1 to N:
For each j from 0 to i-1:
If dp[j] is true AND s[j:i] is in dictionary:
dp[i] = true
Break (we found one valid path to i, no need to check others).
def wordBreak_dp(s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
# If prefix s[0:j] is valid AND substring s[j:i] is a word
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
Complexity:
- Time: O(N^3). Nested loops O(N^2) + substring slicing O(N).
- Space: O(N) for
dparray.
Optimization: Trie (Prefix Tree)
If the dictionary is huge, checking every s[j:i] in word_set means slicing and hashing many substrings that cannot possibly be words. If we have words like “apple”, “app”, “ap”, checking them independently is also redundant, because they share a prefix.
We can store the dictionary in a Trie.
For every position i that is reachable (dp[i] is true), walk the Trie forward along s[i:]. Each time the walk reaches a node that ends a word, the position after it becomes reachable. The moment the next character has no child in the Trie, stop: no dictionary word starts with that prefix. This is a form of pruning.
Trie Implementation
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
root = TrieNode()
for word in wordDict:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
if dp[i]:
node = root
for j in range(i, n):
if s[j] not in node.children:
break
node = node.children[s[j]]
if node.is_word:
dp[j + 1] = True
return dp[n]
Complexity Analysis:
- Time: O(N × L + C), where L is the length of the longest dictionary word (no walk can go deeper than L) and C is the total number of characters in the dictionary (to build the Trie). Without the Trie, the plain DP does O(N^2) substring checks.
- Space: O(C) for the Trie.
Whether the Trie is faster than a hash set in practice depends on the dictionary and the language runtime. In Python, a hash set with the inner loop bounded by L is often just as fast, so measure on your own data before switching.
Deep Dive: The Aho-Corasick Algorithm
While not necessary for Word Break, the Aho-Corasick algorithm is the natural evolution of the Trie idea. It turns the Trie into a finite state machine that finds all occurrences of all dictionary words in a text in O(N + C + matches) time.
It adds “failure links” to the Trie nodes. If you fail to match a character at a deep node, the failure link takes you to the longest proper suffix of the current match that is also a prefix of some pattern, so the scan never moves backwards in the text.
Why does this matter? Network intrusion detection systems (like Snort) and virus scanners (like ClamAV) need to match thousands of signatures against a stream of bytes. Running a separate search per signature is too slow; Aho-Corasick scans the stream once, in linear time.
Connection to ML: Tokenization and Segmentation
Word Break asks whether a string can be segmented. Tokenizers, query segmenters and decoders ask which segmentation to use, and the same DP over split points answers that question once you attach scores to the pieces. This is the algorithmic core behind the tokenizers described in Tokenization Systems:
- WordPiece (the BERT tokenizer) segments each word at inference time with greedy longest-match-first: take the longest vocabulary entry that matches at the current position, then continue from where it ends. That is the Max Match heuristic below.
- SentencePiece’s unigram model gives every piece a probability and picks the segmentation with the highest total probability using the Viterbi algorithm. That is Word Break with log-probabilities instead of booleans, shown below.
- BPE works differently at inference time: it applies learned merge rules in priority order rather than searching a dictionary, but the result is still a segmentation of the input into vocabulary pieces.
Max Match (greedy)
In languages written without spaces (Chinese, Japanese), forward maximum matching was a classic segmentation baseline:
- Start at the beginning of the string.
- Find the longest word in the dictionary that matches the prefix.
- Emit it, move past it, and repeat.
This is a greedy version of Word Break, and it can paint itself into a corner. With the dictionary {"the", "theta", "table"} and s = "thetable", greedy takes “theta” and is left with “ble”, which is not a word. The DP explores both split points and finds “the table”. WordPiece vocabularies include the single characters, so a match almost always exists; a word that still cannot be matched becomes the unknown token.
Most likely segmentation (Viterbi)
To choose between valid segmentations, score each word. Under a unigram model the probability of a segmentation w1 w2 ... wk is the product P(w1) × P(w2) × ... × P(wk), so in log space we maximize a sum, and dp[i] becomes “best log-probability of segmenting s[:i]”:
import math
class Segmenter:
"""Most likely segmentation of s under a unigram word model (Viterbi)."""
def __init__(self, word_counts, max_word_len=20):
self.counts = word_counts
self.total = sum(word_counts.values())
self.max_len = max_word_len
def log_prob(self, word):
if word in self.counts:
return math.log(self.counts[word] / self.total)
# Unknown word: the longer it is, the less likely it is a real word
return math.log(10.0 / (self.total * 10 ** len(word)))
def segment(self, s):
n = len(s)
best = [0.0] + [-math.inf] * n # best[i] = max log-prob of s[:i]
back = [0] * (n + 1) # back[i] = start of the last word
for i in range(1, n + 1):
for j in range(max(0, i - self.max_len), i):
score = best[j] + self.log_prob(s[j:i])
if score > best[i]:
best[i], back[i] = score, j
words, i = [], n
while i > 0:
words.append(s[back[i]:i])
i = back[i]
return words[::-1]
counts = {"new": 50, "york": 20, "times": 30, "news": 10, "time": 25, "yo": 1, "rk": 1}
print(Segmenter(counts).segment("newyorktimes")) # ['new', 'york', 'times']
The unknown-word penalty is a simple heuristic from Peter Norvig’s well-known word segmentation example: without it, an unknown 12-character chunk would score as well as a short unknown one. Swap the unigram for a bigram model (P(wi | wi-1)) and the state becomes “position plus last word”, which is the same Viterbi idea that classic speech recognizers use to choose word boundaries; see ASR decoding.
Search engines face the same problem with queries typed without spaces (“newyorktimes”). Production query segmenters add entity dictionaries (“New York” is one unit) and user behavior signals on top of the language-model score, then rank the candidate segmentations.
Interview Simulation
Interviewer: “Can you optimize the inner loop?”
You: “Yes. If we know the maximum word length in the dictionary is K, we only need to check j from i-1 down to i-K. That cuts the work from O(N^2) to O(N × K) substring checks.”
Interviewer: “What if the dictionary is too large to fit in memory?” You: “This is a classic System Design pivot.
- Bloom Filter: Keep a Bloom filter of the dictionary in memory. If it says ‘No’, the word is definitely absent and we skip the disk. If it says ‘Yes’, we confirm on disk. Most non-words never touch the disk.
- Sharding: Shard the dictionary by prefix or by a hash of the word.
- DAWG (Directed Acyclic Word Graph): A Trie shares prefixes. A DAWG (a minimized automaton) shares suffixes too, so it is much smaller than a plain Trie for a natural-language dictionary.”
Interviewer: “How would you handle typos?”
You: “We would need Fuzzy Word Break. Instead of checking s[j:i] in word_set, we accept s[j:i] if some dictionary word is within edit distance k. That explodes the search space, so we’d use a BK-Tree or the SymSpell algorithm to query ‘words within distance k’ efficiently.”
Multi-Language Implementation
C++
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
int n = s.length();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
Detailed Walkthrough: Tracing “leetcode”
Let’s trace the DP algorithm with s = "leetcode" and wordDict = ["leet", "code"].
Initialization:
dp array of size 9 (length 8 + 1).
dp[0] = True (Base case).
dp[1..8] = False.
Iteration i = 1 (‘l’):
j=0:dp[0]is True.s[0:1](“l”) in dict? No.
Iteration i = 4 (‘leet’):
j=0:dp[0]is True.s[0:4](“leet”) in dict? Yes.- Set
dp[4] = True. Break.
Iteration i = 5 (‘leetc’):
j=0:dp[0]True. “leetc” in dict? No.- …
j=4:dp[4]True.s[4:5](“c”) in dict? No.
Iteration i = 8 (‘leetcode’):
j=0:dp[0]True. “leetcode” in dict? No.- …
j=4:dp[4]True.s[4:8](“code”) in dict? Yes.- Set
dp[8] = True. Break.
Result: dp[8] is True. Return True.
Advanced Variant: Word Break II (Reconstructing Sentences)
What if we need to return all possible sentences, not just a boolean?
Example: s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]
Output: ["cats and dog", "cat sand dog"]
This requires Backtracking with Memoization.
def wordBreak_II(s: str, wordDict: List[str]) -> List[str]:
word_set = set(wordDict)
memo = {}
def backtrack(start):
if start in memo:
return memo[start]
if start == len(s):
return [""]
sentences = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
# Get all sentences from the rest of the string
rest_sentences = backtrack(end)
for sentence in rest_sentences:
if sentence:
sentences.append(word + " " + sentence)
else:
sentences.append(word)
memo[start] = sentences
return sentences
return backtrack(0)
Complexity:
- Time: Exponential in the worst case, because the output itself can be exponential. For
s = "aaaa...a"withdict = ["a", "aa"], the number of sentences grows like the Fibonacci numbers. - Space: Proportional to the total size of all results.
Advanced Variant: Minimum Number of Words
Problem: Break the string so that the number of spaces is minimized. Example: “applepenapple” -> “apple pen apple” (2 spaces). If the dictionary also has “applepen”, then “applepen apple” (1 space) is better.
Solution: BFS (Breadth-First Search). We want the shortest path in the graph of split points.
- Nodes: Indices
0ton. - Edges:
i -> jifs[i:j]is a word. - Weight: 1 (each word is 1 step).
from collections import deque
def minSpaces(s, wordDict):
word_set = set(wordDict)
n = len(s)
queue = deque([(0, 0)]) # (index, count)
visited = {0}
while queue:
index, count = queue.popleft()
if index == n:
return count - 1 # Spaces = Words - 1
for end in range(index + 1, n + 1):
if end not in visited and s[index:end] in word_set:
visited.add(end)
queue.append((end, count + 1))
return -1
Complexity: O(N^2) substring checks, O(N) space. BFS guarantees the shortest path (fewest words). Replace the unit weights with costs and you get the general partition DP below.
Appendix A: Proof of Correctness
Let P(i) be the proposition that dp[i] is true exactly when s[0...i-1] is segmentable.
Base Case: P(0) is true (empty string).
Inductive Step: Assume P(k) is true for all k < i.
- If
dp[i]is set to true, there is somej < iwithdp[j]true ands[j:i]a word. By hypothesiss[0...j-1]is segmentable, sos[0...i-1]is that segmentation plus one more word. - Conversely, if
s[0...i-1]is segmentable, lets[j:i]be the last word of some segmentation. Thens[0...j-1]is segmentable, sodp[j]is true by hypothesis, and the loop setsdp[i]when it reaches thatj.
Thus P(i) is true.
Appendix B: Comprehensive Test Cases
- Standard: “leetcode”, [“leet”, “code”] -> True
- Reuse: “applepenapple”, [“apple”, “pen”] -> True
- Fail: “catsandog”, [“cats”, “dog”, “sand”, “and”, “cat”] -> False
- Overlap: “aaaaaaa”, [“aaaa”, “aaa”] -> True
- Empty: “”, [“a”] -> True (the constraints say s.length >= 1, but it is good to know)
- No Solution: “a”, [“b”] -> False
- Long String: A string of 1000 ‘a’s with [“a”] -> True (tests recursion depth if not iterative).
- Case Sensitivity: “LeetCode”, [“leet”, “code”] -> False (usually).
- Symbols: “leet-code”, [“leet”, “code”, “-“] -> True.
Appendix C: Related DP Patterns
Word Break belongs to the prefix partition DP family: dp[i] = best over j < i of (dp[j] combined with cost(j, i)).
- Palindrome Partitioning II: minimum cuts so every piece is a palindrome.
- Text Justification (minimum raggedness): Word Break with a cost per line.
- Most likely segmentation: the Viterbi segmenter above.
A related but different family is interval DP (dp[i][j] over substrings), which covers Matrix Chain Multiplication, Minimum Cost to Cut a Stick and Burst Balloons.
Space-Time Trade-offs
| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion | O(2^N) | O(N) | Exponential on inputs like “aaaa…ab” |
| Memoization | O(N^3) | O(N) | N^2 substring checks, each O(N); recursion depth limit |
| Iterative DP | O(N^3), or O(N × K^2) with max word length K | O(N) | No stack overflow; store parents to reconstruct |
| Trie | O(N × K) after an O(C) build | O(C) | Prunes dead prefixes early |
| Bloom filter for the dictionary | Same as the DP | A few bits per word | False positives need a confirm step |
Interview Tip: If the interviewer asks “Optimize for memory”, suggest the Bloom filter or a DAWG. If they ask “Optimize for speed”, bound the inner loop by K or use the Trie.
Conclusion
Word Break is more than just a LeetCode Medium. It is the gateway to Computational Linguistics.
- It teaches us Dynamic Programming (optimizing overlapping subproblems).
- It introduces Tries (efficient string storage).
- It leads directly to Tokenization and most-likely segmentation (Viterbi).
- It scales up to Spell Checkers and Search Engines.
FAQ
How do you solve the Word Break problem?
Use dynamic programming where dp[i] indicates whether s[0:i] can be segmented into dictionary words. For each position i, check all positions j less than i where dp[j] is true and s[j:i] exists in the dictionary. If any such j exists, set dp[i] to true. The answer is dp[n] where n is the string length. Use a hash set for O(1) average-case dictionary lookups.
What is the time complexity of the Word Break DP solution?
O(N squared) substring checks in the worst case, where N is the string length: for each of the N positions, we may check up to N previous positions. Counting the cost of slicing and hashing each substring, the plain version is O(N cubed). Bounding the inner loop by the maximum word length in the dictionary reduces the practical constant. Using a Trie allows early termination when no dictionary word matches the current prefix.
How does a Trie optimize the Word Break solution?
A Trie allows checking all dictionary words starting at a given position in a single character-by-character traversal, pruning branches early when no words match the current prefix. This avoids redundant substring creation and hash lookups, and is especially beneficial when the dictionary contains many words with shared prefixes or when the dictionary is very large.
How does Word Break relate to NLP tokenization?
Tokenizers solve segmentation problems. WordPiece (used by BERT) segments each word with greedy longest-match-first against its vocabulary. SentencePiece’s unigram model gives every piece a probability and picks the most likely segmentation with the Viterbi algorithm, which is Word Break with log-probabilities instead of booleans. BPE works differently: it applies learned merge rules in priority order. Tries are a common way to find all vocabulary pieces that start at a position.