Where it runs
1. The problem
You have one long run of letters with no spaces, like "leetcode", and a dictionary of known words, like ["leet", "code"]. The question is simple: can you cut the run into whole words that are all in the dictionary? You may use the same word as many times as you like. The empty string counts as cut too: it holds zero words.
"leetcode" cuts into "leet" and "code", so the answer is yes. "applepenapple" cuts into "apple", "pen", "apple", with "apple" used twice, so the answer is yes again.
Now "catsandog" with the dictionary ["cats", "dog", "sand", "and", "cat"]. Try a split: "cats", then "and", then "og" is left, and that is not a word. Try "cat", "sand", and "og" is left again. Every cut leaves a tail, so the answer is no. You can't just take the first word that fits. You need to know whether the rest of the string can be cut into words.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedwordBreak("catsdog", ["cat", "cats", "dog"])Can "catsdog" be cut into dictionary words? ok[0] is true: the empty prefix needs no words.
Bars: how many dictionary checks started at each position of the string.
One operation is one dictionary check. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ)O(n²)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- can the string be split into dictionary words
- segment a string using a word list
- boolean reachable at each cut position
- glued text needs word boundaries
Looks similar, isn't
- DP on subsequences (LIS / LCS / edit distance)
That lines up two separate sequences. This one splits a single string.
- Trie (prefix tree)
A trie makes the dictionary lookup fast. The splitting logic above it stays the same.
- Backtracking
Backtracking lists every valid split. The table only answers whether one exists.
- Hash set / map
The dictionary is usually a set. The table is what stops a suffix being retried.
n characters with words up to m give O(nm). A set or a trie keeps the lookup near O(1).
On LeetCode
Problems that cut a string into pieces from a list, or into valid codes, and ask whether it works, in how many ways or at what lowest cost. ok[i] says the first i letters split cleanly, and it comes from any earlier cut j where ok[j] is true and the piece from j to i is valid.
The lesson task. Put the words in a Set so each piece check is O(1) on average.
The pieces are one digit from 1 to 9 or two digits from 10 to 26, and the table counts ways where the lesson says yes or no.
The table holds the fewest leftover letters for each prefix. It is the previous prefix plus one, or an earlier prefix when a dictionary word fills the gap.
You list every split. Backtrack over the cuts and memoize the sentences for each start position.