Word Break
The problem
Decide whether a string can be split into one or more words from a dictionary of nonempty strings. Dictionary words can be reused. Treat an empty input as segmentable.
Example
s = "rainbowrain", dictionary = ["rain", "bow"] → true
Need a hint?
Ask whether each prefix can end with a dictionary word.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Let dp[0] be true. For each endpoint, test candidate start positions up to the maximum dictionary word length earlier. If dp[start] is true and s[start:end] is a dictionary word, mark the endpoint reachable. Return dp[len(s)]. Account for substring copying when analyzing runtime.
Complexity
O(nL²) time with O(L)-cost substring creation and hashing, O(n + dictionary size) space; L is maximum word length.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.