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 Sam K., 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

More Recursion practice problems

See all Recursion problems →