Word Break II

Hard · Tries · Explanation and code example

Dynamic Programming (Top-Down) Using Trie

How it works

This combines the benefits of Trie-based prefix matching with memoization. The Trie provides efficient character-by-character matching and early termination, while the cache prevents recomputation of results for the same starting positions. This is particularly effective when the dictionary contains many words with common prefixes.

Steps

  1. Build a Trie from all dictionary words.
  2. Create a cache to store results for each starting index.
  3. Define a recursive function that returns all sentences from index i.
  4. At each index, traverse the Trie character by character while building words.
  5. When a word boundary is found in the Trie, recursively get all suffixes and combine with the current word.
  6. Cache and return the results. If a character is not in the Trie, terminate that branch early.

Complexity

  • Time complexity: O(m + n * 2 ^ n)
  • Space complexity: O(m + n * 2 ^ n)

Where n is the length of the string s and m is the sum of the lengths of the strings in the wordDict.

Things to watch for

Not Handling the Base Case Correctly When Building Sentences

When recursion reaches the end of the string, returning an empty list [] instead of a list with an empty string [""] causes all valid sentences to be lost since there's nothing to append the last word to.

Forgetting to Add Space Between Words

When concatenating words to form sentences, forgetting to add spaces between words results in malformed output like "catsand" instead of "cats and".

Using List Instead of Set for Dictionary Lookup

Checking if a substring exists in the word dictionary using a list results in O(m * t) lookup per check instead of O(t). This significantly slows down the solution.

Not Memoizing Results Leading to TLE

Without memoization, the same suffix is recomputed many times, leading to exponential time complexity even when not necessary. This causes Time Limit Exceeded on inputs with many overlapping subproblems.

Modifying Shared State Without Proper Backtracking

When using a shared list to build the current path, forgetting to pop the last word after recursion corrupts the path for other branches.

Python code example

from typing import List
from functools import cache

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.isWord = True

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        trie = Trie()
        for word in wordDict:
            trie.addWord(word)

        cache = {}

        def backtrack(index):
            if index == len(s):
                return [""]
            if index in cache:
                return cache[index]

            res = []
            curr = trie.root
            for i in range(index, len(s)):
                char = s[i]
                if char not in curr.children:
                    break
                curr = curr.children[char]
                if curr.isWord:
                    for suffix in backtrack(i + 1):
                        if suffix:
                            res.append(s[index:i + 1] + " " + suffix)
                        else:
                            res.append(s[index:i + 1])

            cache[index] = res
            return res

        return backtrack(0)

C++ code example

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    void addWord(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (!curr->children.count(c)) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c];
        }
        curr->isWord = true;
    }
};

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        for (const string& word : wordDict) {
            trie.addWord(word);
        }

        unordered_map<int, vector<string>> cache;
        return backtrack(0, s, trie, cache);
    }

private:
    vector<string> backtrack(int index, string& s, Trie& trie, unordered_map<int, vector<string>>& cache) {
        if (index == s.size()) {
            return {""};
        }

        if (cache.count(index)) {
            return cache[index];
        }

        vector<string> res;
        TrieNode* curr = trie.root;

        for (int i = index; i < s.size(); ++i) {
            char c = s[i];
            if (!curr->children.count(c)) {
                break;
            }
            curr = curr->children[c];
            if (curr->isWord) {
                for (const string& suffix : backtrack(i + 1, s, trie, cache)) {
                    if (!suffix.empty()) {
                        res.push_back(s.substr(index, i - index + 1) + " " + suffix);
                    } else {
                        res.push_back(s.substr(index, i - index + 1));
                    }
                }
            }
        }

        return cache[index] = res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations