A catalog slugger stored SKUs as one blob — no spaces. "leetcode" was "leet" then "code". "applepenapple" reused "apple". The intern recursed: from index i, try every dictionary word that prefixes s[i..], then the rest. A dozen-character SKU returned. A long code with overlapping prefixes was still forking prefix trees when the window closed.

Word Break asks whether dictionary words can cover s end to end, reuse allowed. A string already gives prefixes for free. Recursing every match uses that and still pays an exponential tree.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here a set only answers is this slice in the dictionary? so we can mark which indexes a word can land on.

The problem

Given a string s and a list of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.

s = "leetcode",      wordDict = ["leet","code"]                    →  true
s = "applepenapple", wordDict = ["apple","pen"]                    →  true   ("apple" reused)
s = "catsandog",     wordDict = ["cats","dog","sand","and","cat"]  →  false

Note: Reuse is allowed. The dictionary is not a bag you deplete. "applepenapple" is two "apple"s and a "pen", not a missing third token.

Recursing every prefix is the honest brute force

From index i, try every dictionary word that prefixes s[i..]. Recurse on i + word.length(). If any path hits s.length(), yes. Correct. Exponential in overlapping prefixes.

boolean wordBreakDfs(String s, List<String> wordDict) {
    return from(s, 0, new HashSet<>(wordDict));
}

boolean from(String s, int i, Set<String> dict) {
    if (i == s.length()) {
        return true;
    }
    for (String w : dict) {
        if (s.startsWith(w, i) && from(s, i + w.length(), dict)) {
            return true;
        }
    }
    return false;
}

At n = 8 this is a rounding error. At a long blob with overlapping prefixes you paid a tree for a question a boolean array answers: which indexes can a dictionary word already land on?

Boolean array: mark every landing

dp[i] means s[0..i) is already a valid segmentation. dp[0] = true — the empty prefix is covered. Walk i. If dp[i] is false, skip: nothing that starts here continues a covered prefix. If it is true, try each dictionary word, or every s.substring(i, j) against a hash table of the dict. A match sets dp[end]. dp[n] is the answer.

Walk "leetcode" / ["leet","code"]:

s = l e e t c o d e     n = 8
    0 1 2 3 4 5 6 7

dp[0] = true

i=0  reachable
     "leet" matches s[0..]  →  dp[4] = true
     "code" does not
i=1,2,3  not reachable — skip
i=4  reachable
     "leet" does not match s[4..]
     "code" matches          →  dp[8] = true

dp[8] → true

You never fork a path twice. Index 4 is reachable once; "code" is tried once. The Java is that walk, words from reachable i:

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        if (!dp[i]) {
            continue;
        }
        for (String w : dict) {
            int end = i + w.length();
            if (end <= n && s.startsWith(w, i)) {
                dp[end] = true;
            }
        }
        if (dp[n]) {
            return true;
        }
    }
    return dp[n];
}

Time is O(n · W · L) — n indexes, W dictionary words, L characters to compare. Extra space is O(n) for the boolean array, plus the set. Looping j and dict.contains(s.substring(i, j)) paints the same marks; that is O(n²) substring checks instead of W words per landing.

Note: You do not need the words themselves. Reconstructing the sentence is Word Break II. Skipping !dp[i] is the failure you must not skip: a match that does not continue a covered prefix is a dead start.

What interviewers usually poke next

  • Word Break II. Return every valid sentence, not a boolean. Name it and stop unless they switch the prompt. This array only answers reachability.
  • catsandog. cat, cats, sand, and and all land somewhere. None cover the last index. Overlapping prefixes are why the tree exploded; they are also why you mark landings instead of hoping one DFS path is enough.
  • Empty s, empty dict. n = 0 leaves dp[0] true. A nonempty s with an empty dict never leaves index 0. Do not invent a special case unless they ask.
  • Memo DFS. Cache “does index i succeed?” so you do not re-expand a landing. Same marks as the array, more stack. Say it, then go back to the boolean walk.

You are done with this problem when you can walk "leetcode" / ["leet","code"] on a whiteboard with dp[0] and dp[4], and you can say out loud why the prefix tree is correct, why you do not need it, and why a set is membership rather than a hashing lecture.