Word Break (LeetCode 139): Dynamic Programming Solutions in Python

Word Break (LeetCode 139) asks whether a string can be split into a sequence of words that all appear in a dictionary. The clean answer is dynamic programming over prefixes: a prefix can be built if some shorter buildable prefix is followed by a dictionary word. It runs in O(n times L), where L is the longest word, once you limit how far back you look.

The problem

Given a string s and a list of words wordDict, return true if s can be split into one or more dictionary words. A word may be reused as many times as you like.

Questions to ask the interviewer: can the dictionary contain duplicates, can it be empty, and is the string guaranteed non-empty? (Check the constraints on the problem page.)

Brute force

Try every first word that matches the start of the string, then recurse on the rest. With a string like "aaaaaaaaaab" and the words a, aa, aaa, the recursion revisits the same suffixes many times, so the time is exponential. The fix is to remember the answer for each starting position.

Approach 1: top-down with memoization

Define can(start) as whether the suffix beginning at start can be split. Cache the result.

from functools import lru_cache

def word_break_memo(s, word_dict):
    words = set(word_dict)

    @lru_cache(maxsize=None)
    def can(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and can(end):
                return True
        return False

    return can(0)

Each of the n starting positions is solved once, and each tries up to n end positions, with a slice and a set lookup. That is O(n squared) lookups, or O(n cubed) character work if you count the cost of building each slice. Space is O(n) for the cache and the recursion.

Approach 2: bottom-up dynamic programming

Let dp[i] be true if the first i characters can be split. dp[0] is true, since the empty prefix needs no words. For each end position, look for a start where dp[start] is true and s[start:end] is a word.

def word_break(s, word_dict):
    words = set(word_dict)
    max_len = max((len(w) for w in words), default=0)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for end in range(1, len(s) + 1):
        for start in range(max(0, end - max_len), end):
            if dp[start] and s[start:end] in words:
                dp[end] = True
                break
    return dp[len(s)]

Limiting start to the last max_len positions matters. A dictionary word can't be longer than the longest word, so there's no point checking longer slices. That turns the inner loop into at most L steps, and the whole thing into O(n times L) lookups.

Trace

For s = "leetcode" with ["leet","code"]: dp[0] is true. dp[4] becomes true because dp[0] is true and "leet" is a word. dp[8] becomes true because dp[4] is true and "code" is a word. The answer is dp[8], which is true.

Common mistakes

• Forgetting that words can be reused.
• Returning true as soon as any prefix is a word. The whole string has to be covered.
• Building every slice without the max_len limit, which is correct but slow on long strings.
• Converting the dictionary to a set late, or not at all, so each lookup scans a list.

Edge cases to test

How to explain it in an interview

1. Say the brute force and why it repeats work.
2. State the subproblem: can the prefix of length i be built?
3. Write the recurrence in words, then code the bottom-up version.
4. Mention the max_len limit and give the complexity.
5. Offer the memoized version if the interviewer prefers recursion.

I tested both versions above against a brute-force search on 20,000 random small inputs, plus the three examples in the table, before publishing. A quick random check like that is a good habit when you practice.

Related practice

See our Big O cheat sheet for the complexity terms, the LeetCode Blind 75 list for what to practice next, and the coding interview assistant guide for how to practice.

Talk through your approach aloud while you code. A transcript shows whether you stated the key observation before writing. Follow the employer's rules on AI tools in any live assessment.