Word Break

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a string and a list of dictionary words, decide whether the string can be cut into a sequence of one or more dictionary words. Each word can be used any number of times, and every letter must belong to exactly one word.

    This is a classic "DP over prefixes" question. It looks like string matching, but the hard part is that one early choice (which word to cut first) changes everything after it. Original problem: LeetCode 139.

    Example

    "systemcraft" splits as "sys" + "temcraft". "codecraft" can't be split: every way to start leaves a piece that isn't a word.
    "systemcraft" splits as "sys" + "temcraft". "codecraft" can't be split: every way to start leaves a piece that isn't a word.
    Input:  s = "systemcraft", words = ["system", "craft"]
    Output: true          # "system" + "craft"
    Input:  s = "systemcraft", words = ["sys", "system", "temcraft"]
    Output: true          # "sys" + "temcraft" (not "system" + ...)
    Input:  s = "codecraft", words = ["code", "cod", "raft"]
    Output: false

    Constraints (assumed)

    • 1 ≤ length of s ≤ 300.
    • 1 ≤ number of words ≤ 1,000, each 1 to 20 lowercase letters, all distinct.

    What this question tests

    • Spotting overlapping subproblems: "can the rest of the string from position j be split?" is asked again and again by different cut sequences.
    • Turning that into a clean prefix DP (or memoised recursion) instead of exponential backtracking.
    • Small but real optimisations: a hash set for the dictionary and the max-word-length bound.

    Questions to ask first

    1. Can a word be reused? (Here: yes.)
    2. Do you need just yes/no, or the actual split, or all splits? All splits is a much bigger output (see Variants).
    3. How big are the string and the dictionary? Long strings with short words favour the max-length bound; a huge dictionary favours a trie.
    4. Is the empty string a valid input? If so, it is trivially splittable.