We have a string and a dictionary. The question is whether we can break the string into pieces where every piece is a word in the dictionary. We can reuse words as many times as we want, and we need to cover the entire string with no characters left over.

This is a decision problem: can we find at least one valid segmentation? We don't need to return the actual segmentation, only true or false.

The problem has overlapping subproblems. Whether the substring from index i to the end can be segmented does not depend on how we reached i, so that answer can be reused across every segmentation path that lands at i. That repetition is what dynamic programming eliminates.

Key Constraints:

Intuition

Start at the beginning of the string and try every possible first word. If the prefix s[0..k] matches a dictionary word, recursively check whether the remaining string s[k+1..end] can also be segmented. If any branch succeeds, return true. If no branch works, return false.

This explores a decision tree. At each position in the string, we branch into all dictionary words that match starting at that position, and we want any path through the tree that consumes the entire string.

Algorithm

Example Walkthrough

Code

The same suffix gets recomputed many times through different segmentation paths. Storing the result for each starting index the first time it is computed removes that redundancy.

Intuition

The brute force recursion does a lot of duplicate work. The function canBreak(start) only depends on the starting index, and there are only n possible starting indices (0 through n-1). So if we cache the result of canBreak(start) the first time we compute it, every subsequent call with the same start returns immediately.

The logic is identical to the brute force, with a memo table that stores whether each suffix can be segmented. The number of distinct subproblems drops to n, so the work that was exponential becomes polynomial.

Algorithm

Example Walkthrough

Code

The recursion adds overhead from function calls and stack frames. The same subproblems can be computed in bottom-up order with a loop, which removes the recursion entirely.

Intuition

Instead of recursion, we can fill a DP table iteratively. Define dp[i] as "can the first i characters of s be segmented using the dictionary?" The answer we want is dp[n], where n is the length of s.

The recurrence is straightforward: dp[i] is true if there exists some j < i such that dp[j] is true AND the substring s[j..i-1] is in the dictionary. In other words, we can form the first i characters if we can form the first j characters AND the remaining chunk from j to i is a valid word.

Algorithm

Example Walkthrough

Code

The hash-set DP rebuilds a substring for every (i, j) pair, and each rebuild copies up to n characters. A trie lets us test all candidate words starting at a position by walking the string one character at a time, with no substring allocation.

Intuition

A trie stores the dictionary so that shared prefixes share nodes. Starting from any index i, we can follow s[i], s[i+1], ... down the trie one character at a time. If the walk reaches a word-end node after consuming the character at index k, then s[i..k] is a dictionary word, so if dp[i] is true we set dp[k + 1] to true. We never build a substring or hash one; each step is a single child lookup.

This keeps the same dp[i] meaning as the bottom-up DP (can the first i characters be segmented), but replaces the inner hash-set loop, which does O(n) substring work per check, with a walk down the trie that stops as soon as the path runs out of matching nodes. The walk from any index cannot go further than the longest dictionary word, so the inner work is bounded by L, the maximum word length.

Algorithm

Example Walkthrough

Code