These are the notes for DSA episode 71. Your phone's space bar breaks mid-message, and your friend receives sundaylight. Their phone knows the words sun, sunday, day and daylight. Can it cut the message back into dictionary words? We try greedy first (grab the longest word: a wrong answer on screen), then every first word recursively (correct, then Time Limit Exceeded on 40 a's and a b), draw the key insight on the string, ok[i] = some j with ok[j] and s[j..i) a word, type it live, print the sentence, and make it handle a 20,000-letter page in milliseconds by only looking back as far as the longest word. Then three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| The broken space bar | In code |
|---|---|
The glued message sundaylight |
the string s |
| The words the phone knows | the dictionary wordDict |
| Putting the spaces back | cutting s into dictionary words |
| "sun daylight" | a valid segmentation |
| A word can appear twice ("apple pen apple") | words may be reused |
| Every letter must belong to a word | the cut must cover the whole string |
Every word, from zero
- String / substring: a sequence of characters; a substring
s[j..i)is the letters from indexjup to, but not including,i(Javas.substring(j, i)). - Prefix: the first
iletters of a string,s[0..i). There aren + 1prefixes, from the empty one to the whole string. - Dictionary: the list of allowed words.
- Segmentation: a way to cut the string into consecutive pieces.
- Greedy: always take the choice that looks best right now, never undoing it.
- Hash set: a set with O(1) average
contains; much faster than searching a list. - State:
i, the length of the prefix. - Recurrence:
ok[i] = OR over j of (ok[j] AND s[j..i) is a word). - Base case:
ok[0] = true: the empty prefix needs no cutting. - maxLen: the length of the longest dictionary word; the last word can't be longer.
- Memoization: caching the answer of a recursive call by its arguments.
Problem statement
Word Break (LeetCode 139). Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused. 1 ≤ s.length ≤ 300, 1 ≤ wordDict.length ≤ 1000, 1 ≤ word length ≤ 20.
| s | wordDict | Answer |
|---|---|---|
leetcode |
[leet, code] |
true |
applepenapple |
[apple, pen] |
true (apple reused) |
catsandog |
[cats, dog, sand, and, cat] |
false |
sundaylight |
[sun, sunday, day, daylight] |
true (sun daylight) |
a |
[b] |
false |
aaaa |
[a, aa] |
true |
dogs |
[dog] |
false |
Obvious idea 1: greedy, longest word first
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
int i = 0;
while (i < s.length()) {
String best = null;
for (String w : words)
if (s.startsWith(w, i) && (best == null || w.length() > best.length()))
best = w;
if (best == null) return false;
i += best.length();
}
return true;
}
public static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code")));
System.out.println(wordBreak("applepenapple", List.of("apple", "pen")));
System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
System.out.println(wordBreak("sundaylight", List.of("sun", "sunday", "day", "daylight")));
}
}
true
true
false
false
The fourth answer is wrong. Greedy grabbed sunday and was left with light, which isn't a word; the right cut starts with the shorter sun. A first word can only be judged by what's left after it.
Obvious idea 2: try every first word
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
return can(s, 0, new HashSet<>(words));
}
static boolean can(String s, int start, Set<String> dict) {
if (start == s.length()) return true;
for (int end = start + 1; end <= s.length(); end++)
if (dict.contains(s.substring(start, end)) && can(s, end, dict))
return true;
return false;
}
public static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code")));
System.out.println(wordBreak("applepenapple", List.of("apple", "pen")));
System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
System.out.println(wordBreak("sundaylight", List.of("sun", "sunday", "day", "daylight")));
System.out.println(wordBreak("a", List.of("b")));
System.out.println(wordBreak("aaaa", List.of("a", "aa")));
System.out.println(wordBreak("dogs", List.of("dog")));
}
}
true
true
false
true
false
true
false
All correct. Now 40 a's and a b, with the words a, aa, aaa, aaaa, aaaaa. The b can never match, so the answer is false, but first the recursion tries every way to cut the 40 a's (billions):
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
return can(s, 0, new HashSet<>(words));
}
static boolean can(String s, int start, Set<String> dict) {
if (start == s.length()) return true;
for (int end = start + 1; end <= s.length(); end++)
if (dict.contains(s.substring(start, end)) && can(s, end, dict))
return true;
return false;
}
public static void main(String[] args) {
String s = "a".repeat(40) + "b";
List<String> dict = List.of("a", "aa", "aaa", "aaaa", "aaaaa");
long t0 = System.nanoTime();
boolean ok = wordBreak(s, dict);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("41 letters: " + ok + ", " + ms + " ms");
}
}
Time Limit Exceeded (stopped after 25 s)
Why is it slow?
can(start)depends on one number:start. The string and the dictionary never change.a + aa,aa + aandaaaall land onstart = 3, and the whole rest is recomputed each time.- There are only
n + 1 = 42different starts.
The key insight: ok[i] over prefixes
| Step | Rule |
|---|---|
| State | ok[i] = can the first i letters be cut into words? |
| Last word | s[j..i) for some j < i |
| Recurrence | ok[i] = true if some j has ok[j] and s[j..i) in the dictionary |
| Base | ok[0] = true |
| Answer | ok[n] |
By hand: sundaylight
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| prefix ends after | (empty) | s | u | n | d | a | y | l | i | g | h | t |
| ok[i] | ✓ | · | · | ✓ sun | · | · | ✓ sunday / sun+day | · | · | · | · | ✓ sun+daylight |
For ok[11]: from j = 6 the last word would be light (not a word); from j = 3 it is daylight, and ok[3] is true. ✓.
Solution in Java
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (ok[j] && dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code")));
System.out.println(wordBreak("applepenapple", List.of("apple", "pen")));
System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
System.out.println(wordBreak("sundaylight", List.of("sun", "sunday", "day", "daylight")));
System.out.println(wordBreak("a", List.of("b")));
System.out.println(wordBreak("aaaa", List.of("a", "aa")));
System.out.println(wordBreak("dogs", List.of("dog")));
}
}
true
true
false
true
false
true
false
Printing the sentence
Store where the last word started, from[i] (-1 = impossible), then walk back from n.
import java.util.*;
public class Main {
static String sentence(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
int[] from = new int[n + 1];
Arrays.fill(from, -1);
from[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (from[j] >= 0 && dict.contains(s.substring(j, i))) {
from[i] = j;
break;
}
if (from[n] < 0) return "no sentence";
LinkedList<String> parts = new LinkedList<>();
for (int i = n; i > 0; i = from[i]) parts.addFirst(s.substring(from[i], i));
return String.join(" ", parts);
}
public static void main(String[] args) {
System.out.println(sentence("sundaylight", List.of("sun", "sunday", "day", "daylight")));
System.out.println(sentence("ilovechaiandsamosa", List.of("i", "love", "chai", "and", "samosa", "sam")));
System.out.println(sentence("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
}
}
sun daylight
i love chai and samosa
no sentence
A whole page: look back only maxLen letters
With every j from 0, each i makes up to i substrings, each up to i letters long: O(n³) letters copied. A 20,000-letter page:
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (ok[j] && dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
String s = "a".repeat(40) + "b";
List<String> dict = List.of("a", "aa", "aaa", "aaaa", "aaaaa");
long t0 = System.nanoTime();
boolean ok = wordBreak(s, dict);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("41 letters: " + ok + ", " + ms + " ms");
StringBuilder sb = new StringBuilder();
while (sb.length() < 20000) sb.append("chaiandsamosa");
List<String> menu = List.of("chai", "and", "samosa", "sam");
t0 = System.nanoTime();
ok = wordBreak(sb.toString(), menu);
ms = (System.nanoTime() - t0) / 1000000;
System.out.println(sb.length() + " letters: " + ok + ", " + ms + " ms");
}
}
41 letters: false, 1 ms
Time Limit Exceeded (stopped after 25 s)
The last word is a dictionary word, so it is at most maxLen letters: j ≥ i - maxLen.
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int maxLen = 0;
for (String w : words) maxLen = Math.max(maxLen, w.length());
int n = s.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = Math.max(0, i - maxLen); j < i; j++)
if (ok[j] && dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
String s = "a".repeat(40) + "b";
List<String> dict = List.of("a", "aa", "aaa", "aaaa", "aaaaa");
long t0 = System.nanoTime();
boolean ok = wordBreak(s, dict);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("41 letters: " + ok + ", " + ms + " ms");
StringBuilder sb = new StringBuilder();
while (sb.length() < 20000) sb.append("chaiandsamosa");
List<String> menu = List.of("chai", "and", "samosa", "sam");
t0 = System.nanoTime();
ok = wordBreak(sb.toString(), menu);
ms = (System.nanoTime() - t0) / 1000000;
System.out.println(sb.length() + " letters: " + ok + ", " + ms + " ms");
}
}
41 letters: false, 0 ms
20007 letters: true, 11 ms
And the examples still pass:
true
true
false
true
false
true
false
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Word break: ok[i] = the first i letters can be cut into words. Look back at most maxLen letters.
bool wordBreak(const string& s, const vector<string>& words) {
unordered_set<string> dict(words.begin(), words.end());
size_t maxLen = 0;
for (auto& w : words) maxLen = max(maxLen, w.size());
int n = s.size();
vector<bool> ok(n + 1, false);
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = max(0, i - (int)maxLen); j < i; j++)
if (ok[j] && dict.count(s.substr(j, i - j))) { ok[i] = true; break; }
return ok[n];
}
int main() {
cout << boolalpha;
cout << wordBreak("leetcode", {"leet", "code"}) << "\n";
cout << wordBreak("applepenapple", {"apple", "pen"}) << "\n";
cout << wordBreak("catsandog", {"cats", "dog", "sand", "and", "cat"}) << "\n";
cout << wordBreak("sundaylight", {"sun", "sunday", "day", "daylight"}) << "\n";
cout << wordBreak(string(40, 'a') + "b", {"a", "aa", "aaa", "aaaa", "aaaaa"}) << "\n";
}
true
true
false
true
false
The same solution in Python
# Word break: ok[i] = the first i letters can be cut into words. Look back at most max_len letters.
def word_break(s, words):
dict_ = set(words)
max_len = max(map(len, words))
n = len(s)
ok = [False] * (n + 1)
ok[0] = True
for i in range(1, n + 1):
for j in range(max(0, i - max_len), i):
if ok[j] and s[j:i] in dict_:
ok[i] = True
break
return ok[n]
print(word_break("leetcode", ["leet", "code"]))
print(word_break("applepenapple", ["apple", "pen"]))
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))
print(word_break("sundaylight", ["sun", "sunday", "day", "daylight"]))
print(word_break("a" * 40 + "b", ["a", "aa", "aaa", "aaaa", "aaaaa"]))
True
True
False
True
False
Three real bugs
Bug 1: no ok[j] check.
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
}
}
true
true is wrong: it only checked that the string ends with a word (dog), never whether catsan before it could be cut.
Bug 2: j starts at 1.
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (ok[j] && dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code")));
}
}
false
false is wrong: the first word must start at position 0, so ok[0] must be read.
Bug 3: new boolean[n].
import java.util.*;
public class Main {
static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int n = s.length();
boolean[] ok = new boolean[n];
ok[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (ok[j] && dict.contains(s.substring(j, i))) {
ok[i] = true;
break;
}
return ok[n];
}
public static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code")));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8
at Main.wordBreak(Main.java:12)
at Main.main(Main.java:18)
There are n + 1 prefixes; ok[8] means all 8 letters of leetcode.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Greedy, longest word | O(n × D) | O(1) | fast but wrong |
| Every first word | O(2^n) | O(n) stack | 41 letters: Time Limit Exceeded |
| Prefix DP, every j | O(n³) (n² substrings of up to n letters) | O(n) | 20,000 letters: Time Limit Exceeded |
| Prefix DP + maxLen L | O(n × L²) | O(n) + dictionary | 20,000 letters: ~13 ms |
| Prefix DP + trie | O(n × L) | O(n) + trie | no substrings at all |
D is the number of words. On LeetCode (n ≤ 300) every DP version passes; maxLen is what makes it scale.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Greedy, longest word first | false for sundaylight |
sunday leaves light |
DP over every last word |
No ok[j] check |
true for catsandog |
only the last word checked | ok[j] && dict.contains(...) |
j starts at 1 |
false for leetcode |
ok[0] never used |
j from 0 (or i - maxLen) |
new boolean[n] |
ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8 |
n + 1 prefixes |
new boolean[n + 1] |
List.contains for the dictionary |
slow on big dictionaries | O(D) per check | HashSet |
Every j on long strings |
Time Limit Exceeded | O(n³) letters copied | j ≥ i - maxLen |
Mini project: put the spaces back
Read a dictionary file and a glued sentence; print the sentence with spaces, or no sentence. Extension: when several sentences exist, prefer the one with the fewest words (store words[i], the fewest words for prefix i, and take a minimum instead of OR).
Practice
1. Decode Ways (LeetCode 91). Digits map to letters (1 = A ... 26 = Z). Count the decodings of "226".
2. Word Break II (LeetCode 140). Return every sentence.
3. Count the sentences for "aaaa" with [a, aa].
Solutions
Decode ways is the same prefix shape with + instead of OR: one-digit and two-digit last pieces. Word Break II memoizes the list of sentences for each start position (there can be exponentially many, so you can't avoid that output size). "aaaa" has 5 sentences.
import java.util.*;
public class Main {
// Decode Ways (LeetCode 91): ways[i] = ways to decode the first i digits (+ instead of OR).
static int numDecodings(String s) {
int n = s.length();
int[] ways = new int[n + 1];
ways[0] = 1;
for (int i = 1; i <= n; i++) {
if (s.charAt(i - 1) != '0') ways[i] += ways[i - 1];
if (i >= 2) {
int two = Integer.parseInt(s.substring(i - 2, i));
if (two >= 10 && two <= 26) ways[i] += ways[i - 2];
}
}
return ways[n];
}
// Word Break II (LeetCode 140): every sentence, memoized on the start position.
static Map<Integer, List<String>> memo = new HashMap<>();
static List<String> sentences(String s, int start, Set<String> dict) {
if (memo.containsKey(start)) return memo.get(start);
List<String> res = new ArrayList<>();
if (start == s.length()) res.add("");
for (int end = start + 1; end <= s.length(); end++) {
String w = s.substring(start, end);
if (!dict.contains(w)) continue;
for (String rest : sentences(s, end, dict)) res.add(rest.isEmpty() ? w : w + " " + rest);
}
memo.put(start, res);
return res;
}
public static void main(String[] args) {
System.out.println(numDecodings("12"));
System.out.println(numDecodings("226"));
System.out.println(numDecodings("06"));
System.out.println(sentences("catsanddog", 0, new HashSet<>(List.of("cat", "cats", "and", "sand", "dog"))));
memo.clear();
System.out.println(sentences("aaaa", 0, new HashSet<>(List.of("a", "aa"))).size());
}
}
2
3
0
[cat sand dog, cats and dog]
5
4. Concatenated Words (LeetCode 472). For each word, run word break with the other words as the dictionary.
Quick quiz
pineapplepen with [pine, apple, pen, pineapple]. A) No: pineapple leaves pen B) Yes: pine + apple + pen C) Yes, only as pineapple + pen D) No: pine leaves applepen
Answer
B. ok[4] (pine), ok[9] (pine + apple, and pineapple) and ok[12] (+ pen) are true. C is wrong because it isn't the only way.
Interview questions
- Why does greedy fail? A long first word can leave a remainder that can't be cut (
sunday+light). - State and recurrence?
ok[i] = ∃ j < i: ok[j] && s[j..i) ∈ dict,ok[0] = true. - Why a HashSet? O(1) average lookup instead of O(D).
- Complexity? O(n² × n) naive; O(n × L²) with
maxLen; O(n) space. - How do you return the sentence? Store the start of the last word,
from[i], and walk back. - Word Break II's complexity? Output-sensitive: there can be exponentially many sentences (
"aaaa...a"). - Top-down version? Memoize
can(start)in aBoolean[]; the same complexity. - How does a trie help? From each
j, walk the trie forward letter by letter, so no substrings are built and the walk stops as soon as no word continues.
Glossary
| Term | Meaning |
|---|---|
Substring s[j..i) |
letters from j up to, not including, i |
| Prefix | The first i letters; n + 1 of them |
| Dictionary | The allowed words |
| Segmentation | Cutting a string into consecutive words |
| Greedy | Take the best-looking choice now, never undo |
| HashSet | A set with O(1) average lookups |
| State | i: the prefix length |
| Recurrence | ok[i] = ok[j] AND word(j, i) for some j |
| Base case | ok[0] = true |
| maxLen | The longest word's length |
| Memoization | Caching a call's answer by its arguments |
| Trie | A tree of letters for prefix lookups (episode 45) |
Summary
- Greedy can pick the wrong word; trying every first word is right but exponential.
ok[i] = trueif someok[j]is true ands[j..i)is a word;ok[0] = true; answerok[n].from[i]remembers the cut so the sentence can be printed.- Look back only
maxLenletters:O(n × L²)time,O(n)space. - Next episode: palindromes, the longest palindromic substring and cutting a string into palindromes.