Problem 54 · Dynamic Programming

Word Break

MediumClassic DSA & systems

01Problem

Given a string s and a dictionary of words, return whether s can be segmented into a sequence of one or more dictionary words.

02Key insight

dp[i] is true if some dictionary word ends at i and dp[start] is true. Bound the inner loop by the longest dictionary word to avoid O(n^2) substring checks.

03Solution

solution.pypython10 lines

def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    max_len = max(map(len, words), default=0)
    dp = [True] + [False] * len(s)
    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[-1]

Try it first.

TimeO(n * L * L)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert word_break("leetcode", ["leet","code"]) is True
assert word_break("catsandog", ["cats","dog","sand","and","cat"]) is False
assert word_break("", ["a"]) is True
assert word_break("aaab", ["a","aa"]) is False

04Staff-level follow-up

Tokenizing user queries at scale? Use a trie (or Aho-Corasick) to walk all dictionary matches from each start in one pass, and score segmentations with word frequencies (Viterbi) instead of a boolean.