How to Solve the Word Break Problem Efficiently Using DP and Trie

The most efficient way to solve the Word Break problem combines dynamic programming with a Trie data structure to achieve O(n·L) time complexity instead of O(n²), where n is the string length and L is the average word length.

The Word Break problem is a classic algorithmic challenge that asks whether a given string can be segmented into a sequence of dictionary words. The kdn251/interviews repository provides clean implementations of both baseline and optimized solutions, including a reusable Trie class and multiple DP-based approaches.

Understanding the Word Break Problem

The problem requires determining if an input string s can be broken into valid words from a provided dictionary wordDict. A naïve recursive solution tries every possible split, resulting in exponential time complexity. The standard optimization uses dynamic programming (DP) to store intermediate results, but lookup performance remains a bottleneck when using simple hash sets for large dictionaries.

The Baseline DP Solution

The repository contains a straightforward DP implementation in leetcode/dynamic-programming/WordBreak.java. This approach uses a boolean array dp where dp[i] indicates whether the substring s[0…i-1] can be segmented using dictionary words.

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

This solution runs in O(n²) time where n is the length of the string, with the inner dictionary lookup dominating the runtime. For large dictionaries or long strings, the repeated hash lookups and substring operations create significant overhead.

Optimizing with a Trie Data Structure

Storing the dictionary in a Trie (prefix tree) enables faster prefix queries and early termination when no match exists. The repository provides a complete Trie implementation in company/google/ImplementTrie.java with insert, search, and startsWith methods.

Unlike a HashSet, which requires O(1) lookup time that can degrade with collisions, a Trie allows checking whether a substring is a valid dictionary word in O(L) time, where L is the word length. More importantly, the Trie structure lets you stop early when the current prefix does not exist in the dictionary, eliminating unnecessary iterations through the inner loop.

The Combined DP and Trie Implementation

By merging the DP approach with Trie traversal, you replace the inner j loop with a single walk through the Trie. For each position i where dp[i] is true, traverse the Trie forward from index i while characters match. When you encounter a node marked as the end of a word (node.last == true), mark the corresponding DP position as reachable.

// Build the Trie from the dictionary
Trie trie = new Trie();
for (String w : wordDict) {
    trie.insert(w);
}

// DP + Trie combined algorithm
public boolean wordBreakWithTrie(String s, Trie trie) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        if (!dp[i]) continue;               // only start from reachable positions
        TrieNode node = trie.root;           // start from the root of the Trie
        for (int j = i; j < n; j++) {
            char c = s.charAt(j);
            if (!node.map.containsKey(c)) break; // no further prefix possible
            node = node.map.get(c);
            if (node.last) dp[j + 1] = true;     // found a word ending at j
        }
    }
    return dp[n];
}

This implementation leverages the TrieNode structure from company/google/ImplementTrie.java, utilizing the map field for character navigation and the last boolean to identify complete words.

Complexity Analysis

The combined DP and Trie approach offers significant performance improvements over the baseline solution:

• Time Complexity: O(n·L) where n is the string length and L is the average word length in the dictionary. In the worst case with maximum word length m, this becomes O(n·m), which is typically much faster than the O(n²) baseline when m << n.
• Space Complexity: O(n + totalTrieNodes) — the DP array requires O(n) space, while the Trie requires O(totalTrieNodes) proportional to the total characters in the dictionary.

Summary

• The Word Break problem requires determining if a string can be segmented into dictionary words.
• The baseline DP solution in leetcode/dynamic-programming/WordBreak.java achieves O(n²) time using a HashSet for lookups.
• Integrating a Trie from company/google/ImplementTrie.java reduces the time complexity to O(n·L) by enabling efficient prefix matching and early termination.
• The optimized algorithm walks the Trie forward from each reachable DP index, marking new positions only when complete words are found.
• This approach scales gracefully for large dictionaries and long input strings, making it suitable for production-level implementations.

Frequently Asked Questions

Why use a Trie instead of a HashSet for the Word Break problem?

A Trie provides O(L) prefix lookup with early termination capabilities, whereas a HashSet requires checking every possible substring start position. When the current character sequence does not exist in the Trie, you can immediately break the inner loop rather than continuing to check longer substrings. This structural advantage eliminates unnecessary comparisons, especially when the dictionary contains many words with shared prefixes.

What is the exact time complexity of the DP plus Trie approach?

The combined approach runs in O(n·L) time, where n is the length of the input string and L represents the average word length in the dictionary. In the worst-case scenario where you must check the maximum word length m at every position, the complexity becomes O(n·m). This is substantially faster than the baseline O(n²) DP solution when the average word length is significantly smaller than the string length.

Can this solution handle very large dictionaries efficiently?

Yes, the Trie structure scales efficiently with dictionary size because it compresses shared prefixes into common nodes. Rather than storing each word independently in a HashSet, the Trie reduces memory overhead for dictionaries with common prefixes (such as English vocabulary). The space complexity remains O(totalTrieNodes), which is bounded by the total number of characters across all dictionary words.

How does early termination work during Trie traversal?

During the inner loop traversal starting from index i, the algorithm checks node.map.containsKey(c) before descending to the next character. If the character does not exist in the current Trie node's map, the loop breaks immediately because no dictionary word can form with the current prefix. This prevents wasted iterations through the remaining substring positions, directly improving performance over the baseline approach that must check every possible substring length.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}