AlgoViz
HomeBacktracking

Word Break

Medium

Split off a dictionary word, recurse on the rest

Problem

Given a string and a dictionary, return all sentences formed by inserting spaces so each word is in the dictionary.

In simple words

Mark each cut point reachable if some earlier reachable point is followed by a dictionary word.

The idea

Try every prefix of the remaining string; whenever a prefix is a dictionary word, take it and recurse on what is left. Memoising by starting index stops the same suffix being re-explored down different branches, which is the difference between fast and exponential.

The trick

  • Put the dictionary in a hash set so each prefix check is O(1).
  • Memoise on the start index — the answer for a suffix never depends on how you got there.
  • Reaching the end of the string means the sentence built so far is valid.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — s='catsanddog', dict=['cat','cats','and','sand','dog'] Values: 0.

1/2
Optimal
timeO(2^n)spaceO(n)
1f(start):2  if start==n: output current sentence3  for end in start..n-1:4    if s[start..end] in dict: add word; f(end+1); remove word

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "leetcode", words = ["leet","code"]
Output:
true
Explanation:
Splits into leet + code.

Example 2

Input:
s = "applepenapple", words = ["apple","pen"]
Output:
true
Explanation:
apple + pen + apple.

Example 3

Input:
s = "catsandog", words = ["cats","dog","sand","and","cat"]
Output:
false
Explanation:
No clean split → false.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.