medium

Word Break

Check whether a string can be split into a sequence of words from a given dictionary.

1. Define the problem

Word Break

You are given a string s and a list of words called a dictionary. Return true if s can be cut into a sequence of dictionary words, with no letters left over. Words may be reused as many times as you like. The trick is to work left to right and keep one true-or-false answer per cut position : can the letters up to here be built out of dictionary words? A position is reachable when some earlier reachable position is followed by a dictionary word that ends right here.

Constraints

  • 1 ≤ s.length ≤ 300
  • 1 ≤ wordDict.length ≤ 1000
  • 1 ≤ wordDicti.length ≤ 20
  • s and the dictionary words contain only lowercase English letters
  • All dictionary words are different from each other

Example

Inputs = "catsand", wordDict = ["cat", "cats", "and", "sand"]
Outputtrue

Explanation "catsand" can be cut into "cat" + "sand", and both are in the dictionary.

2. Know the words first

In plain terms

Dictionary
The list of allowed words. Here it is only the words you are given, not a real English dictionary.
Cut position
A gap between letters, counted from 0 (before the first letter) up to the length of the string (after the last letter).
Reachable
A cut position is reachable when every letter before it has already been covered by whole dictionary words.
Set
A collection built for fast "is this in here?" checks, so looking a word up does not mean scanning the whole list.
3. Visualize the solution

Mark every cut position that whole words can reach

Mark every cut position that whole words can reach
Statusinit

Only position 0 starts reachable — no letters covered yet.

What happens in this step

s = "catsand"
dictionary = cat, cats, and, sand

Every position is marked F except position 0, which is T. Position 0 means "no letters used so far", which is always possible.
Step 1 of 6

Steps to visualize

  1. The row is the 8 cut positions of "catsand", from 0 (before the first letter) to 7 (after the last).
  2. T means that position is reachable using whole dictionary words; F means it is not.
  3. Position 0 starts as T because covering no letters at all needs no words.
  4. For each position, look back at every earlier position that is already T.
  5. If the letters between that earlier position and this one form a dictionary word, this position becomes T.
  6. The box marks the piece of the string being checked.
  7. The answer is the mark on the last position.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Mark every cut position that whole words can reach
Statusinit

Only position 0 starts reachable — no letters covered yet.

What happens in this step

s = "catsand"
dictionary = cat, cats, and, sand

Every position is marked F except position 0, which is T. Position 0 means "no letters used so far", which is always possible.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const reachable = new Array(s.length + 1).fill(false);
  reachable[0] = true;

  for (let end = 1; end <= s.length; end += 1) {
    for (let start = 0; start < end; start += 1) {
      if (reachable[start] && words.has(s.slice(start, end))) {
        reachable[end] = true;
        break;
      }
    }
  }

  return reachable[s.length];
}
Time
O(n^2 * k) where n is the string length and k the longest word
Space
O(n + total dictionary size)
6. Test cases

Test cases

InputExpectedCovers
s = "catsand", wordDict = ["cat", "cats", "and", "sand"]trueexample from the description
s = "leetcode", wordDict = ["leet", "code"]truea clean split into exactly two words
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]falsea split that looks promising but leaves letters over
s = "a", wordDict = ["a"]truesmallest possible input
s = "aaaaa", wordDict = ["b"]falseno dictionary word appears in the string at all
s = "applepenapple", wordDict = ["apple", "pen"]truethe same word is reused

Keep reading