Skip to main content

140. Word Break II

hard

Given a string and a dictionary, return every way to break the string into valid dictionary words separated by spaces. The hard cousin of Word Break — you must enumerate every sentence, not just check feasibility.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Constraints

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.
  • Input is generated in a way that the length of the answer doesn't exceed 10^5.

Examples

Example 1

Input
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output
["cats and dog","cat sand dog"]

Example 2

Input
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output
["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Put wordDict into a hash set for O(1) lookups.

Hint 2

Top-down memoized recursion: backtrack(start) returns all sentences that segment s[start..].

Hint 3

Base case: start == s.length -> return [""] (one empty sentence).

Hint 4

For each end such that s[start..end] is in the dictionary, recurse on backtrack(end) and prepend the word to each result. Memoize by start.

Solution approach

Reveal approach

Put wordDict into a hash set. Define backtrack(start) -> list of sentences from s[start..]. Base case: start == s.length -> return [""]. Otherwise: results = []. For end from start + 1 to s.length, let word = s.substring(start, end). If word in dictionary, recurse on backtrack(end). For each sub-sentence sub, push word + (sub.isEmpty() ? "" : " " + sub) to results. Memoize results by start so each suffix is segmented once. Time can be exponential because the answer itself can be exponential; memoization caches each suffix's result list. Space includes the cache.

Complexity

Time
O(n^2 + 2^n) — output bounded
Space
O(n^2)

Related patterns

  • recursion
  • memoization
  • trie

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Word Break II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →