Word Break

Medium · 1-D Dynamic Programming · Explanation and code example

Dynamic Programming (Trie)

How it works

The normal DP checks every word at every index, which can waste time comparing strings again and again.

A Trie stores all dictionary words like a prefix tree, so from any starting index i in s, we can walk forward character-by-character and quickly know:

whether the current prefix matches some dictionary word path
and when we hit a complete word (is_word = true)

We still use DP:

dp[i] = can we break the suffix s[i:] into dictionary words?
If from i we can reach some j where s[i..j] is a word, then dp[i] = dp[j+1]

Trie helps us find valid words starting at i efficiently.

Steps

Build a Trie from all words in wordDict.
Create a boolean DP array dp of size n + 1 where n = len(s).
- dp[n] = true (empty suffix is always valid)
Let t be the maximum word length in the dictionary (use it as a bound).
Fill DP from right to left:
- For each index i from n down to 0:
  - Try all end positions j from i to min(n-1, i+t-1):
    - If s[i..j] is a word in the Trie, set dp[i] = dp[j+1]
    - If dp[i] becomes true, stop early for this i
Return dp[0].

Complexity

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

Where n is the length of the string s, m is the number of words in wordDict and t is the maximum length of any word in wordDict.

Things to watch for

Off-by-One Error in DP Array Initialization

The DP array needs size n + 1 to represent the state after processing all characters. Using size n causes index-out-of-bounds when checking dp[n] as the base case.

Checking Substring Beyond String Length

When iterating through possible word matches, failing to check if the word extends beyond the string causes substring errors or incorrect matches.

Not Converting wordDict to a Set for Efficient Lookup

Using a list for the word dictionary when checking substrings against it results in O(m) lookup time per check, causing TLE on large inputs.

Python code example

from typing import List

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

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, s, i, j):
        node = self.root
        for idx in range(i, j + 1):
            if s[idx] not in node.children:
                return False
            node = node.children[s[idx]]
        return node.is_word

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

        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        t = 0
        for w in wordDict:
            t = max(t, len(w))

        for i in range(len(s), -1, -1):
            for j in range(i, min(len(s), i + t)):
                if trie.search(s, i, j):
                    dp[i] = dp[j + 1]
                    if dp[i]:
                        break

        return dp[0]

C++ code example

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool is_word = false;
};

class Trie {
public:
    TrieNode* root;

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

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_word = true;
    }

    bool search(string& s, int i, int j) {
        TrieNode* node = root;
        for (int idx = i; idx <= j; ++idx) {
            if (!node->children.count(s[idx])) {
                return false;
            }
            node = node->children[s[idx]];
        }
        return node->is_word;
    }
};

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

        int n = s.length();
        vector<bool> dp(n + 1, false);
        dp[n] = true;

        int maxLen = 0;
        for (string w : wordDict) {
            maxLen = max(maxLen, (int)w.size());
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < min(n, i + maxLen); ++j) {
                if (trie.search(s, i, j)) {
                    dp[i] = dp[j + 1];
                    if (dp[i]) break;
                }
            }
        }

        return dp[0];
    }
};

Source and license

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

Check the explanation on LeetCode Watch NeetCode on YouTube

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

Resume recall check

Browse all problem explanations