Return whether s can be segmented into a sequence of one or more dictionary words (words may be reused).
Before you code
dp[i] says whether the first i characters can be segmented. It is true if some earlier split point j is segmentable and s[j:i] is a word.
Hints
- dp[0] = true.
- For each i, check j from i − 1 down to i − (longest word length), using a set for word lookups.
- Return dp[n].
Production & complexity notes
When solving Word break on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in One-dimensional problems to reinforce the underlying pattern.
What it practices
Prefix states with a membership test, from One-dimensional problems.