LeetCode 139 Word Break: DP, BFS and Trie Solutions (Plus Word Break II)

Word Break is a favourite because it sits at the meeting point of three topics: strings, dynamic programming and graph reachability. A candidate who only knows one view tends to get stuck on follow-ups; one who sees all three can switch to a Trie when the dictionary is huge, to BFS when asked for the fewest words, and to DFS when asked for every sentence.

This guide builds the DP from the recursion, adds the max-word-length optimisation most solutions miss, dry-runs the classic examples, and then covers BFS, the Trie walk and Word Break II, with code in Python, C++ and Java. If DP still feels like magic, read Coin Change first; Word Break has exactly the same "what is the last piece?" structure.

The Problem: Segment a String into Dictionary Words

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. The same word can be used multiple times.

Constraints on LeetCode: 1 ≤ s.length ≤ 300, 1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 20, lowercase letters only, all dictionary words distinct. The word-length cap of 20 matters: it's what makes the max-length optimisation meaningful.

Why the Greedy Split Fails

The first idea many people have is to scan left to right and cut as soon as the prefix is a word (shortest match), or take the longest word that matches (longest match). Both are wrong:

• Longest match on "goalspecial": "goals" matches, leaving "pecial", which can't be split. But "goal" + "special" works.
• Shortest match on the same string: "go" matches, leaving "alspecial", which also fails.

The choice of where to cut affects what remains, and no local rule picks correctly every time. You need to try every possible first word and remember which suffixes (or prefixes) you've already proven impossible. That's DP.

Recursion and Memoization

Define canBreak(i): can the suffix s[i:] be segmented? Try every word that starts at i; if any leads to a breakable remainder, return true. The empty suffix is trivially breakable.

from functools import lru_cache
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        max_len = max(map(len, words))
        n = len(s)

        @lru_cache(maxsize=None)
        def can_break(i: int) -> bool:
            if i == n:
                return True
            for j in range(i + 1, min(n, i + max_len) + 1):
                if s[i:j] in words and can_break(j):
                    return True
            return False

        return can_break(0)

Why memoization is essential

Without the cache, a string like "aaaaaaaaaaaaaaaaaaab" with the dictionary ["a", "aa", "aaa", "aaaa"] explodes. Every prefix of a's can be split in many ways, each split reaches the same suffix, and each suffix eventually fails at the 'b'. The number of paths grows exponentially (roughly like a Fibonacci-style count of compositions). With memoization, each of the n + 1 start indices is solved once, so the failure is discovered once and reused.

Recursion depth here is at most n = 300, which is safe even in Python.

Bottom-Up DP for Word Break

Flip the direction: dp[i] = true if the prefix s[0:i] (first i characters) can be segmented.

1. Base: dp[0] = true. The empty prefix needs no words.
2. Transition: dp[i] = true if there is a j < i with dp[j] = true and s[j:i] in the dictionary. In words: the last word is s[j:i], and everything before it is breakable.
3. Bound: the last word is at most L characters long (L = longest dictionary word), so only check j ≥ i − L.
4. Answer: dp[n].

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        max_len = max(map(len, words))
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(max(0, i - max_len), i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[n]

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        int maxLen = 0;
        for (const auto& w : wordDict) maxLen = max(maxLen, (int)w.size());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= max(0, i - maxLen); --j) {
                if (dp[j] && words.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

In C++ and Java, the inner loop runs j from i − 1 downward, which tries short last words first. Either direction is correct; checking dp[j] before building the substring is what saves time, because substr/substring allocate.

Alternative inner loop: iterate over words

When the dictionary is small but words are long, loop over words instead of split points:

def word_break_by_words(s, word_dict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for w in word_dict:
            k = len(w)
            if k <= i and dp[i - k] and s.startswith(w, i - k):
                dp[i] = True
                break
    return dp[n]

This is O(n · m · L) for m words, with no substring allocation (startswith with an offset compares in place). It mirrors Coin Change exactly: words are coins, and their lengths are denominations, with the extra condition that the characters must match.

Dry Run: "leetcode" and "catsandog"

s = "leetcode", words = {leet, code}, L = 4

s = "catsandog", words = {cats, dog, sand, and, cat}, L = 4

All other entries are false. dp[9] is false, so the answer is false. Notice how the table explains why: the only breakable long prefix is "catsand", and "og" can't be a word. That's a nice way to narrate the result to an interviewer.

BFS: Word Break as Graph Reachability

Each index 0..n is a node. There's an edge i → j when s[i:j] is a dictionary word. The string can be segmented if node n is reachable from node 0. BFS with a visited array processes each index at most once.

from collections import deque

def word_break_bfs(s, word_dict):
    words = set(word_dict)
    max_len = max(map(len, words))
    n = len(s)
    visited = [False] * (n + 1)
    q = deque([0])
    visited[0] = True
    while q:
        i = q.popleft()
        if i == n:
            return True
        for j in range(i + 1, min(n, i + max_len) + 1):
            if not visited[j] and s[i:j] in words:
                visited[j] = True
                q.append(j)
    return False

Same complexity as the DP. Its advantage is a free bonus: BFS reaches each index in the fewest edges, so a level-counting version returns the minimum number of words directly. If the interviewer asks for that follow-up, switching to BFS is elegant. The graph framing is the same one used in BFS and DFS graph problems.

Trie Approach: Walk the Dictionary Along the String

The DP above builds a substring and hashes it for every candidate split. A Trie avoids that. From each index already known to be reachable, walk the Trie character by character along s. Every time you land on a node that ends a word, mark the next index reachable. Stop as soon as the Trie has no child for the next character, since no dictionary word continues that way.

END = '__end__'                         # multi-char key never collides with a letter

def word_break_trie(s, word_dict):
    root = {}
    for w in word_dict:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node[END] = True

    n = len(s)
    reach = [False] * (n + 1)
    reach[0] = True
    for start in range(n):
        if not reach[start]:
            continue
        node = root
        for end in range(start, n):
            node = node.get(s[end])
            if node is None:
                break                    # no word continues with this prefix
            if END in node:
                reach[end + 1] = True
    return reach[n]

class Solution {
    struct Node {
        int next[26];
        bool end = false;
        Node() { fill(next, next + 26, -1); }
    };
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<Node> trie(1);
        for (const string& w : wordDict) {
            int cur = 0;
            for (char ch : w) {
                int c = ch - 'a';
                if (trie[cur].next[c] == -1) {
                    trie[cur].next[c] = trie.size();
                    trie.emplace_back();
                }
                cur = trie[cur].next[c];
            }
            trie[cur].end = true;
        }
        int n = s.size();
        vector<bool> reach(n + 1, false);
        reach[0] = true;
        for (int start = 0; start < n; ++start) {
            if (!reach[start]) continue;
            int cur = 0;
            for (int i = start; i < n; ++i) {
                cur = trie[cur].next[s[i] - 'a'];
                if (cur == -1) break;
                if (trie[cur].end) reach[i + 1] = true;
            }
        }
        return reach[n];
    }
};

The node indices are stored in a vector rather than as pointers, so emplace_back reallocating the vector doesn't invalidate anything (we always re-index through trie[cur]). The walk from each start is at most L steps, so the total is O(n · L) character steps plus O(total dictionary characters) to build the Trie. For more on Trie implementation choices (array vs hash-map children), see the Trie data structure guide.

Word Break II (LeetCode 140): Return Every Sentence

Same input, but now return all possible sentences. For s = "catsanddog" and ["cat", "cats", "and", "sand", "dog"], the answer is ["cats and dog", "cat sand dog"].

The key difference: the output itself can be exponentially large. For a string of 20 a's with dictionary ["a", "aa"], the number of sentences is a Fibonacci number (10,946). No algorithm can be polynomial when the answer is exponential, so the goal is to avoid wasted work, not to be polynomial.

Memoized DFS by start index

from functools import lru_cache
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        n = len(s)

        @lru_cache(maxsize=None)
        def sentences_from(i: int) -> tuple:
            if i == n:
                return ("",)                     # one way: the empty sentence
            result = []
            for j in range(i + 1, n + 1):
                w = s[i:j]
                if w in words:
                    for rest in sentences_from(j):
                        result.append(w + (" " + rest if rest else ""))
            return tuple(result)

        return list(sentences_from(0))

Returning tuples from the cached function prevents a subtle bug: if the cached value were a list and some caller mutated it, every other caller would see the change.

Pruning dead ends

Memoization already ensures a suffix that yields no sentences is explored only once. A further trick is to run the Word Break 139 DP first and return an empty list immediately if dp[n] is false. That catches adversarial inputs like "aaaa…ab" before any sentence-building starts. Some interviewers specifically look for this.

class Solution {
    unordered_set<string> words;
    unordered_map<int, vector<string>> memo;
    string s;

    const vector<string>& from(int i) {
        auto it = memo.find(i);
        if (it != memo.end()) return it->second;
        vector<string> res;
        if (i == (int)s.size()) {
            res.push_back("");
        } else {
            for (int j = i + 1; j <= (int)s.size(); ++j) {
                string w = s.substr(i, j - i);
                if (!words.count(w)) continue;
                for (const string& rest : from(j))
                    res.push_back(rest.empty() ? w : w + " " + rest);
            }
        }
        return memo[i] = move(res);
    }
public:
    vector<string> wordBreak(string str, vector<string>& wordDict) {
        s = str;
        words = unordered_set<string>(wordDict.begin(), wordDict.end());
        memo.clear();
        return from(0);
    }
};

Returning a const reference into an unordered_map is safe here because references to elements of an unordered_map stay valid across inserts (only iterators are invalidated by rehashing). That's a detail a C++-focused interviewer might ask about.

Word Break II is essentially backtracking with a cache. If you'd rather not cache sentence lists (they can be huge), the alternative is plain backtracking that builds one path at a time, pruned by a precomputed "can the suffix from j be broken?" array.

Complexity Compared

Let n = |s|, L = longest word length, m = number of words, and W = total characters in the dictionary.

For LeetCode's limits (n = 300, L = 20), even the O(n³) version passes. In an interview, the point is to state the honest cost of substring creation and hashing, which many candidates skip by calling the substring check O(1).

How Word Break Shows Up in Interviews

Word Break is commonly reported at Amazon, Google, Microsoft, Meta and Indian product companies. It also has real-world flavour, which interviewers sometimes lean into: segmenting search queries typed without spaces, splitting hashtags like #weloveindia, parsing domain names, or word segmentation for languages written without spaces. Those framings are all this problem plus a scoring function.

A strong walkthrough

1. Clarify: can words be reused? Is the dictionary large? Case sensitivity? Do you want a yes/no, the count, the fewest words, or all sentences?
2. Kill greedy: "goalspecial" with "goals" in the dictionary.
3. Define the state: "dp[i] says whether the first i characters can be split".
4. Code the bounded DP, mentioning the max-length cut.
5. Dry run "catsandog" to show a false case.
6. Complexity with substring cost, then offer the Trie as the optimisation.

Follow-ups to expect

Common mistakes

• Forgetting dp[0] = true, which makes every entry false.
• Off-by-one in slicing: s[j:i] is characters j through i − 1, matching dp's "first i characters" meaning.
• Keeping the dictionary as a list, making each lookup O(m).
• Not breaking out of the inner loop after dp[i] becomes true (correct but slower).
• Word Break II without memoization, which times out on the "aaaa…ab" test.
• Calling substring checks O(1) in the complexity analysis.

Word Break pairs naturally with Longest Increasing Subsequence (another "ends at i" DP) and the string DPs in DP on strings. For more string-handling patterns, see string interview problems. Once you see that the DP, the BFS and the Trie walk are all computing the same reachability, this family stops being three separate problems.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.