Skip to main content
Ace Hired
All coding problems

Word Break

Mediumdynamic programmingDynamic programming over prefixesdynamic-programmingstringshash-set

Maintained by Vikas D, software engineer

You are handed a string `s` and a list of allowed words called `wordDict`. The task is to determine if you can slice `s` into back-to-back chunks so that each chunk is one of the allowed words and the chunks together cover the whole string with nothing left over.

Every character of `s` has to belong to exactly one chunk, and the chunks must appear in order with no gaps or overlaps. You are not asked for the actual breakdown, only whether at least one valid breakdown exists.

A word from the dictionary can be used as many times as you like, or not at all. So if `s` is "aaaa" and the dictionary holds "a", you can reuse "a" four times and the answer is yes.

Return `true` when some valid segmentation exists and `false` when no arrangement of dictionary words spells out `s` exactly.

Examples

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Splitting after position 4 gives "leet" then "code", and both are in the dictionary, so the whole string is covered.

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

The split is "apple" + "pen" + "apple". The word "apple" is reused, which is allowed.

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Every prefix path stalls. "cats" leaves "andog", "cat" leaves "sandog"; neither remainder can be finished with dictionary words, so no full segmentation exists.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and every wordDict[i] contain only lowercase English letters.
  • All words in wordDict are distinct.

Visible test cases

  • wordBreak("leetcode", ["leet","code"]) == true
  • wordBreak("applepenapple", ["apple","pen"]) == true
  • wordBreak("catsandog", ["cats","dog","sand","and","cat"]) == false
  • wordBreak("cars", ["car","ca","rs"]) == true
  • wordBreak("aaaaaaa", ["aaaa","aaa"]) == true
  • wordBreak("ab", ["a","b"]) == true

Hints

Hint 1

Think about prefixes. If you already know the first `start` characters can be segmented, you only need to check whether the slice from `start` to some later index is a dictionary word.

Hint 2

Define a boolean per position: can the prefix ending at this index be split fully? Position 0 (empty prefix) is reachable by definition.

Hint 3

Build positions left to right. An index is reachable if some earlier reachable index is followed by a substring that exists in the word set. Put the dictionary in a hash set so each substring check is fast.

Loading the editor...

Approaches

Brute force recursion

Time O(2^n * k) where n is the string length and k is the substring work, because overlapping starts get re-explored exponentially. · Space O(n) for the recursion stack.

From the current position, try every dictionary word that matches the upcoming characters, consume it, and recurse on the rest. Succeed when you consume the entire string.

  1. Write a helper that takes a start index into `s`.
  2. If start equals the length of `s`, the string is fully consumed, so return true.
  3. For each possible end index, check whether the substring from start to end is in the dictionary set.
  4. If it is, recurse from end; if that recursive call returns true, propagate true.
  5. If no choice from this start leads to success, return false.

Bottom-up dynamic programming

Time O(n^2 * L) where n is the string length and L bounds the cost of slicing and hashing a substring. · Space O(n + total dictionary size) for the dp array and the word set.

Track which prefix lengths are segmentable. A prefix of length `end` is segmentable if some shorter segmentable prefix of length `start` is followed by a dictionary word spanning start to end.

  1. Load `wordDict` into a hash set for constant-time lookups.
  2. Create a boolean array `dp` of length n+1 and set dp[0] = true (the empty prefix is trivially segmentable).
  3. For each end from 1 to n, scan each start from 0 to end-1.
  4. If dp[start] is true and the substring s[start..end] is in the set, mark dp[end] true and stop scanning this end.
  5. After filling the array, return dp[n], which answers whether the whole string is segmentable.

Common mistakes

  • Forgetting to seed dp[0] = true. Without the empty-prefix base case every position stays false and the answer is always false.
  • Plain recursion without memoization times out on inputs like "aaaaaaaa...b" because the same suffixes are recomputed an exponential number of times.
  • Returning true as soon as one dictionary word matches a prefix. A first word fitting does not mean the rest can be segmented; you must confirm the remainder is also segmentable.
  • Bounding the inner substring length by the longest word is a fine optimization, but capping it too aggressively (for example assuming a fixed length) skips valid words and produces wrong answers.
  • Using an array instead of a hash set for the dictionary turns each lookup into a linear scan and pushes the runtime well past what the constraints allow.

Follow-up variations

  • Return every possible segmentation as a list of sentences instead of a single boolean (the Word Break II variant).
  • Count how many distinct segmentations exist rather than just whether one exists.
  • Handle a streaming or very long string where the dictionary is huge, pushing you toward a trie to prune substring checks.
  • Allow at most one character to be ignored or treated as a wildcard and ask whether the string is still segmentable.

Recommended problems

Build the rest of your prep