mafeshsho8lmafeshsho8l
Get Started
All coding questions

Word Break

medium
Blind 75NeetCode 150dynamic-programmingstringshashing

Problem

Given a string and a dictionary of words, decide whether the string can be segmented into a sequence of one or more dictionary words. Words may be reused.

Examples

Input: s = "leetcode", dict = ["leet", "code"]
Output: true
It splits into "leet" and "code".
Input: s = "catsandog", dict = ["cats","dog","sand","and","cat"]
Output: false
No segmentation covers the whole string.

Constraints

  • • 1 <= s.length <= 300
  • • 1 <= dictionary size <= 1000
  • • Dictionary words are unique
Hints(tap to reveal)
  • 1. A prefix is breakable if some earlier breakable cut leaves a dictionary word.
  • 2. Memoize over prefix lengths.
Optimal approach(spoiler)
  1. Let breakable(i) mean the prefix of length i can be segmented.
  2. breakable(0) is true as the empty prefix.
  3. For each i, check every j less than i where breakable(j) and the substring j..i is in the dictionary.
  4. Return breakable at the full length.
  5. O(n^2) time, O(n) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor