Word Break: DP with a Word Dictionary

Word Break is a deceptively important problem. Its solution shape, “can the prefix of length i be built?”, reappears in palindrome partitioning, sentence segmentation, and any segmentation-by-dictionary task. It also tests whether you remember to convert a list into a set for fast membership checks.

The Problem

Given a string s and a dictionary of strings word_dict, return True if s can be segmented into a space-separated sequence of one or more dictionary words. You may reuse the same word multiple times.

Example inputs and outputs:

Input:  s = "leetcode", word_dict = ["leet", "code"]
Output: True
Explanation: "leetcode" = "leet" + "code".

Input:  s = "applepenapple", word_dict = ["apple", "pen"]
Output: True
Explanation: "apple" + "pen" + "apple".

Input:  s = "catsandog", word_dict = ["cats", "dog", "sand", "and", "cat"]
Output: False

Intuition

Define dp[i] as “the first i characters of s can be segmented.” The empty prefix is trivially segmentable, so dp[0] = True. For any larger i, the last word ends at index i; if we knew some split point j < i such that dp[j] is true and s[j:i] is in the dictionary, then dp[i] is also true. Walking i from left to right ensures every dp[j] we need is already computed, giving a clean bottom-up table fill.

Explanation with Example

Take s = "leetcode", word_dict = ["leet", "code"]. Length 8.

dp[0] = True
i=1 "l"        no split works           dp[1] = False
i=2 "le"       no split works           dp[2] = False
i=3 "lee"      no split works           dp[3] = False
i=4 "leet"     dp[0]=True and "leet" in words  dp[4] = True
i=5 "leetc"    dp[4]=True but "c" not in words dp[5] = False
i=6 "leetco"   no valid split           dp[6] = False
i=7 "leetcod"  no valid split           dp[7] = False
i=8 "leetcode" dp[4]=True and "code" in words  dp[8] = True

Final answer: True. The reconstructed segmentation is "leet" + "code".

index  0  1  2  3  4  5  6  7  8
chars     l  e  e  t  c  o  d  e
dp     T  F  F  F  T  F  F  F  T
     ^              ^           ^
     base           |           |
              'leet' matches  'code' matches
              s[0:4], dp[0]   s[4:8], dp[4]

dp[i] = OR over j<i of dp[j] AND s[j:i] in dict

Code

Convert the dictionary to a set first so substring lookups are O(length-of-substring) for hashing rather than O(dictionary-size) for scanning.

def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = 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] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        int n = s.size();
        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] && words.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

Edge Cases

• Empty s: return True. dp[0] handles this.
• Empty dictionary: return True only if s is empty.
• s shorter than the shortest dictionary word: return False unless s itself is a word.
• Duplicate words in word_dict: the set conversion deduplicates safely.
• Repeated characters such as "aaaa...a": tracking the maximum dictionary word length and only looking back that far prevents quadratic blowup from very long substrings.
• Unicode strings: Python handles slicing and hashing correctly without special care.

Complexity Analysis

• Time: O(n^2 * L) in the worst case, where n = len(s) and L is the average substring length being hashed. Each s[j:i] substring creation is O(i - j), and the set lookup is O(i - j) for hashing.
• Space: O(n) for the DP array, plus O(total characters in dictionary) for the set.

The brute force without memoization is exponential. With memoization, the recursive version matches the bottom-up complexity.

How to Explain It in an Interview

Use this script:

1. State the DP definition: dp[i] means “the first i characters are segmentable.”
2. Derive the transition: dp[i] = True if some j has dp[j] = True and s[j:i] is in the dictionary.
3. Mention converting the list to a set up front; interviewers like the small efficiency call-out.
4. Code the bottom-up version, then mention the max-length pruning as an optimization.
5. Trace a small example to demonstrate correctness.
6. State complexity honestly, including substring creation cost.

Bonus signal: contrast this with Word Break II, which asks for all segmentations and therefore requires backtracking rather than a boolean DP.

Related Problems

• Word Break II: enumerate all valid segmentations.
• Palindrome Partitioning: segmentation where every part must be a palindrome.
• Concatenated Words: apply Word Break to every word in a list.
• Decode Ways: a numeric segmentation analogue.

Wrap up

Word Break is the cleanest example of “prefix segmentation” DP. The state, the transition, and the dictionary-set optimization are short enough to memorize, yet they cover a wide family of harder problems. Practice this until the boolean DP feels mechanical, then move on to Word Break II and Palindrome Partitioning where the segmentation produces structured output rather than a yes-or-no answer. Pair this article with /blog/dynamic-programming-introduction for the theoretical grounding.