Word Break
Recognize the pattern
Brute force idea
If you approach Word Break in the most literal way possible, you get this: Try every possible segmentation recursively — exponential. Many substrings are re-evaluated because different segmentations share common prefixes. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
Better approach
A calmer way to see Word Break is this: DP: dp[i] = true if s[0.i-1] can be segmented. For each position i, check all j < i: if dp[j] is true and s[j.i] is in the dictionary, then dp[i] = true. with set lookup. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Key invariant
The truth you want to protect throughout Word Break is this: dp[i] means the first i characters can be perfectly segmented. If dp[j] is true and the substring from j to i is a valid word, then dp[i] is also true. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Watch out for
One easy way to drift off course in Word Break is this: Not recognizing the overlapping subproblems — the recursive approach re-solves the same prefixes many times. Memoization or bottom-up DP eliminates this redundancy. The fix is usually to return to the meaning of each move, not just the steps themselves.