On this page
Description
Can a string with no spaces be split into dictionary words, the way "cookiejarcookie" splits into "cookie jar cookie"? Trying every split is exponential, since a string of n characters can be cut in 2^(n - 1) ways. But whether the rest of the string can be split depends only on where you are, not on how you got there. So ok[i] ("the first i characters can be split") is computed once per position, from earlier positions.
We'll go from simple to more technical:
- The pattern: ok[i] = some j with ok[j] and s[j..i) a word, starting from ok[0] = true.
- A second flavor: fewest words, and why greedy longest-match fails.
- Where segmentation runs in production (hashtags, search queries, languages without spaces).
- What breaks it: occurrence vs tiling, greedy, the empty start, slow lookups.
The approach
Java
boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int n = s.length();
boolean[] ok = new boolean[n + 1]; // ok[i] = the first i characters can be split
ok[0] = true; // the empty prefix
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (ok[j] && dict.contains(s.substring(j, i))) { // split up to j, then one word j..i
ok[i] = true;
break;
}
}
}
return ok[n];
}
Python
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
n = len(s)
ok = [False] * (n + 1) # ok[i] = the first i characters can be split
ok[0] = True # the empty prefix
for i in range(1, n + 1):
for j in range(i):
if ok[j] and s[j:i] in words: # split up to j, then one word j..i
ok[i] = True
break
return ok[n]
A prefix can be split exactly when some earlier prefix can be, followed by one dictionary word. That's the whole recurrence. It also explains a classic trap: "sunflowery" contains "sun", "flow", "flower", "sunflower" and "wer" as substrings, yet can't be split - the pieces must tile the string end to end, which is what chaining ok[j] into ok[i] enforces.
A second flavor: fewest words, and why greedy fails
Store a number instead of a boolean and the same table answers other questions. For the fewest words, best[i] = min over valid j of best[j] + 1, with "impossible" marked by a sentinel:
Java
Arrays.fill(best, Integer.MAX_VALUE);
best[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = Math.max(0, i - maxWordLen); j < i; j++)
if (best[j] != Integer.MAX_VALUE && dict.contains(s.substring(j, i)))
best[i] = Math.min(best[i], best[j] + 1);
Python
best = [float("inf")] * (n + 1)
best[0] = 0
for i in range(1, n + 1):
for j in range(max(0, i - max_word_len), i):
if best[j] != float("inf") and s[j:i] in words:
best[i] = min(best[i], best[j] + 1)
A greedy "take the longest word at each position" is tempting and wrong. For "abcd" with {ab, abc, cd}, it takes "abc" and is stuck on "d", though "ab" + "cd" works. For "aaab" with {aa, aab, a, b}, it takes "aa", then "a", then "b" (3 words), while "a" + "aab" needs 2. Limiting j to the last maxWordLen positions also cuts the work: no word is longer than that.
Where you'll see it
Segmenting text without spaces - Chinese and Japanese tokenization, hashtags, domain names, URL slugs - is word-break DP, usually with scores (word frequencies) instead of booleans so the best segmentation wins. Validating that a byte stream is a sequence of known message formats, or that a code is a concatenation of valid tokens, is the same prefix reachability.
Which tool for which job?
| You need | Use |
|---|---|
| Can it be split? | ok[i] over positions, j limited to the longest word length |
| Fewest words | the same table with min, infinity for impossible |
| How many ways | the same table with +, modulo if asked |
| The most likely split | maximize the sum of log-probabilities of the words |
| Large dictionary, long string | walk a trie forward from every reachable position |
| Every segmentation | enumerate, pruned by "can this suffix be split?" |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Checking that each word occurs somewhere | "sunflowery" passes, though it can't be split | the pieces must tile the string |
| Greedy longest match | fails on "abcd" with {ab, abc, cd} | DP over every split point |
ok[0] left false | nothing is ever reachable | the empty prefix is splittable |
| No word-length bound on j | O(n³) character work | j ≥ i - longest word |
| Boolean splits for real text | "the rapist finder" is as good as "therapist finder" | weight words by frequency |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. "sunflowery" with {sun, flow, flower, sunflower, wer}: every word appears in the string. Why can't it be split?
Show answer
The pieces must cover the string end to end. "sunflower" (or "sun" + "flower") leaves "y", and "sun" + "flow" leaves "ery", which no word starts. No chain of words reaches position 10, so ok[10] stays false even though every word occurs somewhere.
2. For "abcd" with {ab, abc, cd}, why does "take the longest word first" fail?
Show answer
It takes "abc" and is left with "d", which isn't a word. The DP instead marks positions 2 ("ab") and 3 ("abc") reachable, and from 2 reaches 4 with "cd". Greedy commits to one split; DP keeps every reachable split point.
3. How does the table change to find the fewest words?
Show answer
Store counts instead of booleans: best[0] = 0, "impossible" elsewhere, and best[i] = min over valid j of best[j] + 1. The answer is best[n], or -1 if it's still impossible.
Key takeaways
- ok[i] = the first i characters can be split; ok[i] is true if some ok[j] is true and s[j..i) is a word.
- ok[0] = true seeds everything; pieces must tile the string exactly.
- Greedy longest-match fails; the DP checks every split point.
- Swap the boolean for a count or minimum to count segmentations or find the fewest words.
- Limit j to the longest word length (or use a trie) to cut the cost.