Word Break
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

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
- Can a word be reused? (Here: yes.)
- Do you need just yes/no, or the actual split, or all splits? All splits is a much bigger output (see Variants).
- How big are the string and the dictionary? Long strings with short words favour the max-length bound; a huge dictionary favours a trie.
- Is the empty string a valid input? If so, it is trivially splittable.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.