140. Word Break II

How to solve Word Break II (LeetCode 140): the approach in brief

The 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.

Pattern

Word Break II is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Word Break Style) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Determine if string can be segmented into dictionary words using DP.

Approach outline

1. Consider using dynamic programming to break down the problem into smaller subproblems related to substring segmentation.
2. Think about how you can use a 1D DP array where each position represents whether the substring up to that index can form valid sentences.
3. To generate all possible sentences instead of just a boolean answer, try to store not just true/false but the actual possible word combinations at each index.

Complexity

The reference solution runs in O(2^n * n) time and O(2^n * n) space.

Asked at

Word Break II has been reported in interviews at Facebook, Amazon, Bloomberg, ByteDance, Google, Microsoft.