139. Word Break

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

The problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Pattern

Word Break 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 if there is a way to build up the solution incrementally by checking smaller segments of the string before tackling the entire string.
2. Think about using a one-dimensional boolean array where each position indicates whether the substring up to that index can be segmented into dictionary words.
3. At each index, try to find if there is a previous index where the substring from that previous index to the current index forms a valid word and the substring before that previous index was also valid.

Complexity

The reference solution runs in O(n * L) time and O(n + D) space.

Asked at

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