SyntaxPilot
Courses/DSA and Coding Problems/Lesson 71
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 71 of 90

Word break

queued

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 index j up to, but not including, i (Java s.substring(j, i)).
  • Prefix: the first i letters of a string, s[0..i). There are n + 1 prefixes, 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 + a and aaa all land on start = 3, and the whole rest is recomputed each time.
  • There are only n + 1 = 42 different 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

  1. Why does greedy fail? A long first word can leave a remainder that can't be cut (sunday + light).
  2. State and recurrence? ok[i] = ∃ j < i: ok[j] && s[j..i) ∈ dict, ok[0] = true.
  3. Why a HashSet? O(1) average lookup instead of O(D).
  4. Complexity? O(n² × n) naive; O(n × L²) with maxLen; O(n) space.
  5. How do you return the sentence? Store the start of the last word, from[i], and walk back.
  6. Word Break II's complexity? Output-sensitive: there can be exponentially many sentences ("aaaa...a").
  7. Top-down version? Memoize can(start) in a Boolean[]; the same complexity.
  8. 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] = true if some ok[j] is true and s[j..i) is a word; ok[0] = true; answer ok[n].
  • from[i] remembers the cut so the sentence can be printed.
  • Look back only maxLen letters: O(n × L²) time, O(n) space.
  • Next episode: palindromes, the longest palindromic substring and cutting a string into palindromes.