20 minute read

The fundamental string segmentation problem that powers spell checkers, search engines, and tokenizers.

TL;DR

Use DP where dp[i] is true if s[0:i] can be segmented into dictionary words. For each position, check all valid last-word boundaries. Runs in O(N squared) substring checks with O(N) space. Optimize with a Trie for prefix-based dictionary lookup or bound the inner loop by maximum word length. This is the algorithmic foundation of NLP tokenization and extends the state-transition pattern from Decode Ways.

Problem

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

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Intuition

Imagine you are building a search engine. A user types “newyorktimes”. Your system needs to understand that this is likely “new york times”. This process of breaking a continuous stream of characters into meaningful units is called Segmentation or Tokenization.

The “Word Break” problem is the algorithmic core of this task. At every character, we have a choice: “Do I end the current word here?”

If we split “newyorktimes” at index 3 (“new”), we are left with the subproblem of segmenting “yorktimes”. If we split at index 7 (“newyork”), we are left with “times”.

This overlapping subproblem structure screams Dynamic Programming.

Approach 1: Brute Force Recursion

Let canBreak(start_index) be a function that returns true if the suffix s[start_index:] can be segmented.

Algorithm:

  1. Iterate through every possible end index end from start + 1 to length.
  2. Check if the substring s[start:end] is in the dictionary.
  3. If it is, recursively call canBreak(end).
  4. If the recursive call returns true, then the whole string is valid. Return true.
from typing import List

def wordBreak_recursive(s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict) # O(1) lookup
    
    def can_break(start):
        if start == len(s):
            return True
        
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set and can_break(end):
                return True
        
        return False

    return can_break(0)

Complexity:

  • Time: O(2^N). In the worst case (e.g., s = "aaaaab", dict = ["a", "aa", "aaa"]), no segmentation works and we explore every possible partition before giving up.
  • Space: O(N) for recursion depth.

Approach 2: Recursion with Memoization

We are re-calculating the same suffixes. can_break(5) might be called multiple times. Let’s cache it.

def wordBreak_memo(s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    memo = {}
    
    def can_break(start):
        if start in memo:
            return memo[start]
        
        if start == len(s):
            return True
        
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set and can_break(end):
                memo[start] = True
                return True
        
        memo[start] = False
        return False

    return can_break(0)

Complexity:

  • Time: O(N^3). There are N states. For each state, we iterate N times. String slicing/hashing takes O(N). Total N × N × N.
  • Space: O(N) for memoization.

Approach 3: Iterative Dynamic Programming

Let dp[i] be true if the prefix s[0...i-1] (length i) can be segmented.

Initialization:

  • dp[0] = true (Empty string is valid).

Transitions: For each i from 1 to N: For each j from 0 to i-1: If dp[j] is true AND s[j:i] is in dictionary: dp[i] = true Break (we found one valid path to i, no need to check others).

def wordBreak_dp(s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            # If prefix s[0:j] is valid AND substring s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
                
    return dp[n]

Complexity:

  • Time: O(N^3). Nested loops O(N^2) + substring slicing O(N).
  • Space: O(N) for dp array.

Optimization: Trie (Prefix Tree)

If the dictionary is huge, checking every s[j:i] in word_set means slicing and hashing many substrings that cannot possibly be words. If we have words like “apple”, “app”, “ap”, checking them independently is also redundant, because they share a prefix.

We can store the dictionary in a Trie. For every position i that is reachable (dp[i] is true), walk the Trie forward along s[i:]. Each time the walk reaches a node that ends a word, the position after it becomes reachable. The moment the next character has no child in the Trie, stop: no dictionary word starts with that prefix. This is a form of pruning.

Trie Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        root = TrieNode()
        for word in wordDict:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_word = True
            
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(n):
            if dp[i]:
                node = root
                for j in range(i, n):
                    if s[j] not in node.children:
                        break
                    node = node.children[s[j]]
                    if node.is_word:
                        dp[j + 1] = True
                        
        return dp[n]

Complexity Analysis:

  • Time: O(N × L + C), where L is the length of the longest dictionary word (no walk can go deeper than L) and C is the total number of characters in the dictionary (to build the Trie). Without the Trie, the plain DP does O(N^2) substring checks.
  • Space: O(C) for the Trie.

Whether the Trie is faster than a hash set in practice depends on the dictionary and the language runtime. In Python, a hash set with the inner loop bounded by L is often just as fast, so measure on your own data before switching.

Deep Dive: The Aho-Corasick Algorithm

While not necessary for Word Break, the Aho-Corasick algorithm is the natural evolution of the Trie idea. It turns the Trie into a finite state machine that finds all occurrences of all dictionary words in a text in O(N + C + matches) time.

It adds “failure links” to the Trie nodes. If you fail to match a character at a deep node, the failure link takes you to the longest proper suffix of the current match that is also a prefix of some pattern, so the scan never moves backwards in the text.

Why does this matter? Network intrusion detection systems (like Snort) and virus scanners (like ClamAV) need to match thousands of signatures against a stream of bytes. Running a separate search per signature is too slow; Aho-Corasick scans the stream once, in linear time.

Connection to ML: Tokenization and Segmentation

Word Break asks whether a string can be segmented. Tokenizers, query segmenters and decoders ask which segmentation to use, and the same DP over split points answers that question once you attach scores to the pieces. This is the algorithmic core behind the tokenizers described in Tokenization Systems:

  • WordPiece (the BERT tokenizer) segments each word at inference time with greedy longest-match-first: take the longest vocabulary entry that matches at the current position, then continue from where it ends. That is the Max Match heuristic below.
  • SentencePiece’s unigram model gives every piece a probability and picks the segmentation with the highest total probability using the Viterbi algorithm. That is Word Break with log-probabilities instead of booleans, shown below.
  • BPE works differently at inference time: it applies learned merge rules in priority order rather than searching a dictionary, but the result is still a segmentation of the input into vocabulary pieces.

Max Match (greedy)

In languages written without spaces (Chinese, Japanese), forward maximum matching was a classic segmentation baseline:

  1. Start at the beginning of the string.
  2. Find the longest word in the dictionary that matches the prefix.
  3. Emit it, move past it, and repeat.

This is a greedy version of Word Break, and it can paint itself into a corner. With the dictionary {"the", "theta", "table"} and s = "thetable", greedy takes “theta” and is left with “ble”, which is not a word. The DP explores both split points and finds “the table”. WordPiece vocabularies include the single characters, so a match almost always exists; a word that still cannot be matched becomes the unknown token.

Most likely segmentation (Viterbi)

To choose between valid segmentations, score each word. Under a unigram model the probability of a segmentation w1 w2 ... wk is the product P(w1) × P(w2) × ... × P(wk), so in log space we maximize a sum, and dp[i] becomes “best log-probability of segmenting s[:i]”:

import math

class Segmenter:
    """Most likely segmentation of s under a unigram word model (Viterbi)."""
    def __init__(self, word_counts, max_word_len=20):
        self.counts = word_counts
        self.total = sum(word_counts.values())
        self.max_len = max_word_len

    def log_prob(self, word):
        if word in self.counts:
            return math.log(self.counts[word] / self.total)
        # Unknown word: the longer it is, the less likely it is a real word
        return math.log(10.0 / (self.total * 10 ** len(word)))

    def segment(self, s):
        n = len(s)
        best = [0.0] + [-math.inf] * n  # best[i] = max log-prob of s[:i]
        back = [0] * (n + 1)            # back[i] = start of the last word
        for i in range(1, n + 1):
            for j in range(max(0, i - self.max_len), i):
                score = best[j] + self.log_prob(s[j:i])
                if score > best[i]:
                    best[i], back[i] = score, j
        words, i = [], n
        while i > 0:
            words.append(s[back[i]:i])
            i = back[i]
        return words[::-1]

counts = {"new": 50, "york": 20, "times": 30, "news": 10, "time": 25, "yo": 1, "rk": 1}
print(Segmenter(counts).segment("newyorktimes"))  # ['new', 'york', 'times']

The unknown-word penalty is a simple heuristic from Peter Norvig’s well-known word segmentation example: without it, an unknown 12-character chunk would score as well as a short unknown one. Swap the unigram for a bigram model (P(wi | wi-1)) and the state becomes “position plus last word”, which is the same Viterbi idea that classic speech recognizers use to choose word boundaries; see ASR decoding.

Search engines face the same problem with queries typed without spaces (“newyorktimes”). Production query segmenters add entity dictionaries (“New York” is one unit) and user behavior signals on top of the language-model score, then rank the candidate segmentations.

Interview Simulation

Interviewer: “Can you optimize the inner loop?” You: “Yes. If we know the maximum word length in the dictionary is K, we only need to check j from i-1 down to i-K. That cuts the work from O(N^2) to O(N × K) substring checks.”

Interviewer: “What if the dictionary is too large to fit in memory?” You: “This is a classic System Design pivot.

  1. Bloom Filter: Keep a Bloom filter of the dictionary in memory. If it says ‘No’, the word is definitely absent and we skip the disk. If it says ‘Yes’, we confirm on disk. Most non-words never touch the disk.
  2. Sharding: Shard the dictionary by prefix or by a hash of the word.
  3. DAWG (Directed Acyclic Word Graph): A Trie shares prefixes. A DAWG (a minimized automaton) shares suffixes too, so it is much smaller than a plain Trie for a natural-language dictionary.”

Interviewer: “How would you handle typos?” You: “We would need Fuzzy Word Break. Instead of checking s[j:i] in word_set, we accept s[j:i] if some dictionary word is within edit distance k. That explodes the search space, so we’d use a BK-Tree or the SymSpell algorithm to query ‘words within distance k’ efficiently.”

Multi-Language Implementation

C++

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

Java

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

Detailed Walkthrough: Tracing “leetcode”

Let’s trace the DP algorithm with s = "leetcode" and wordDict = ["leet", "code"].

Initialization: dp array of size 9 (length 8 + 1). dp[0] = True (Base case). dp[1..8] = False.

Iteration i = 1 (‘l’):

  • j=0: dp[0] is True. s[0:1] (“l”) in dict? No.

Iteration i = 4 (‘leet’):

  • j=0: dp[0] is True. s[0:4] (“leet”) in dict? Yes.
  • Set dp[4] = True. Break.

Iteration i = 5 (‘leetc’):

  • j=0: dp[0] True. “leetc” in dict? No.
  • …
  • j=4: dp[4] True. s[4:5] (“c”) in dict? No.

Iteration i = 8 (‘leetcode’):

  • j=0: dp[0] True. “leetcode” in dict? No.
  • …
  • j=4: dp[4] True. s[4:8] (“code”) in dict? Yes.
  • Set dp[8] = True. Break.

Result: dp[8] is True. Return True.

Advanced Variant: Word Break II (Reconstructing Sentences)

What if we need to return all possible sentences, not just a boolean? Example: s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"] Output: ["cats and dog", "cat sand dog"]

This requires Backtracking with Memoization.

def wordBreak_II(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    memo = {}

    def backtrack(start):
        if start in memo:
            return memo[start]
        
        if start == len(s):
            return [""]
        
        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                # Get all sentences from the rest of the string
                rest_sentences = backtrack(end)
                for sentence in rest_sentences:
                    if sentence:
                        sentences.append(word + " " + sentence)
                    else:
                        sentences.append(word)
                        
        memo[start] = sentences
        return sentences

    return backtrack(0)

Complexity:

  • Time: Exponential in the worst case, because the output itself can be exponential. For s = "aaaa...a" with dict = ["a", "aa"], the number of sentences grows like the Fibonacci numbers.
  • Space: Proportional to the total size of all results.

Advanced Variant: Minimum Number of Words

Problem: Break the string so that the number of spaces is minimized. Example: “applepenapple” -> “apple pen apple” (2 spaces). If the dictionary also has “applepen”, then “applepen apple” (1 space) is better.

Solution: BFS (Breadth-First Search). We want the shortest path in the graph of split points.

  • Nodes: Indices 0 to n.
  • Edges: i -> j if s[i:j] is a word.
  • Weight: 1 (each word is 1 step).
from collections import deque

def minSpaces(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    queue = deque([(0, 0)]) # (index, count)
    visited = {0}
    
    while queue:
        index, count = queue.popleft()
        if index == n:
            return count - 1 # Spaces = Words - 1
            
        for end in range(index + 1, n + 1):
            if end not in visited and s[index:end] in word_set:
                visited.add(end)
                queue.append((end, count + 1))
                
    return -1

Complexity: O(N^2) substring checks, O(N) space. BFS guarantees the shortest path (fewest words). Replace the unit weights with costs and you get the general partition DP below.

Appendix A: Proof of Correctness

Let P(i) be the proposition that dp[i] is true exactly when s[0...i-1] is segmentable. Base Case: P(0) is true (empty string). Inductive Step: Assume P(k) is true for all k < i.

  • If dp[i] is set to true, there is some j < i with dp[j] true and s[j:i] a word. By hypothesis s[0...j-1] is segmentable, so s[0...i-1] is that segmentation plus one more word.
  • Conversely, if s[0...i-1] is segmentable, let s[j:i] be the last word of some segmentation. Then s[0...j-1] is segmentable, so dp[j] is true by hypothesis, and the loop sets dp[i] when it reaches that j.

Thus P(i) is true.

Appendix B: Comprehensive Test Cases

  1. Standard: “leetcode”, [“leet”, “code”] -> True
  2. Reuse: “applepenapple”, [“apple”, “pen”] -> True
  3. Fail: “catsandog”, [“cats”, “dog”, “sand”, “and”, “cat”] -> False
  4. Overlap: “aaaaaaa”, [“aaaa”, “aaa”] -> True
  5. Empty: “”, [“a”] -> True (the constraints say s.length >= 1, but it is good to know)
  6. No Solution: “a”, [“b”] -> False
  7. Long String: A string of 1000 ‘a’s with [“a”] -> True (tests recursion depth if not iterative).
  8. Case Sensitivity: “LeetCode”, [“leet”, “code”] -> False (usually).
  9. Symbols: “leet-code”, [“leet”, “code”, “-“] -> True.

Word Break belongs to the prefix partition DP family: dp[i] = best over j < i of (dp[j] combined with cost(j, i)).

  • Palindrome Partitioning II: minimum cuts so every piece is a palindrome.
  • Text Justification (minimum raggedness): Word Break with a cost per line.
  • Most likely segmentation: the Viterbi segmenter above.

A related but different family is interval DP (dp[i][j] over substrings), which covers Matrix Chain Multiplication, Minimum Cost to Cut a Stick and Burst Balloons.

Space-Time Trade-offs

Approach Time Space Notes
Recursion O(2^N) O(N) Exponential on inputs like “aaaa…ab”
Memoization O(N^3) O(N) N^2 substring checks, each O(N); recursion depth limit
Iterative DP O(N^3), or O(N × K^2) with max word length K O(N) No stack overflow; store parents to reconstruct
Trie O(N × K) after an O(C) build O(C) Prunes dead prefixes early
Bloom filter for the dictionary Same as the DP A few bits per word False positives need a confirm step

Interview Tip: If the interviewer asks “Optimize for memory”, suggest the Bloom filter or a DAWG. If they ask “Optimize for speed”, bound the inner loop by K or use the Trie.

Conclusion

Word Break is more than just a LeetCode Medium. It is the gateway to Computational Linguistics.

  • It teaches us Dynamic Programming (optimizing overlapping subproblems).
  • It introduces Tries (efficient string storage).
  • It leads directly to Tokenization and most-likely segmentation (Viterbi).
  • It scales up to Spell Checkers and Search Engines.

FAQ

How do you solve the Word Break problem?

Use dynamic programming where dp[i] indicates whether s[0:i] can be segmented into dictionary words. For each position i, check all positions j less than i where dp[j] is true and s[j:i] exists in the dictionary. If any such j exists, set dp[i] to true. The answer is dp[n] where n is the string length. Use a hash set for O(1) average-case dictionary lookups.

What is the time complexity of the Word Break DP solution?

O(N squared) substring checks in the worst case, where N is the string length: for each of the N positions, we may check up to N previous positions. Counting the cost of slicing and hashing each substring, the plain version is O(N cubed). Bounding the inner loop by the maximum word length in the dictionary reduces the practical constant. Using a Trie allows early termination when no dictionary word matches the current prefix.

How does a Trie optimize the Word Break solution?

A Trie allows checking all dictionary words starting at a given position in a single character-by-character traversal, pruning branches early when no words match the current prefix. This avoids redundant substring creation and hash lookups, and is especially beneficial when the dictionary contains many words with shared prefixes or when the dictionary is very large.

How does Word Break relate to NLP tokenization?

Tokenizers solve segmentation problems. WordPiece (used by BERT) segments each word with greedy longest-match-first against its vocabulary. SentencePiece’s unigram model gives every piece a probability and picks the most likely segmentation with the Viterbi algorithm, which is Word Break with log-probabilities instead of booleans. BPE works differently: it applies learned merge rules in priority order. Tries are a common way to find all vocabulary pieces that start at a position.