Word Break
Decide whether a string can be split into a sequence of one or more dictionary words (words may be reused).
A way to picture it
A cat walked across your keyboard and deleted every space. Can you put them back so every chunk is a real word? Work left to right: a prefix is good if a shorter good prefix plus one dictionary word makes it.
How to approach it
ok[i] = true if some ok[j] is true and s[j..i) is a dictionary word. ok[0] = true; the answer is ok[n].
Example
Input: {"s":"leetcode","wordDict":["leet","code"]}. Output: true.
Complexity: O(n²) time and O(n) space. Each end position checks every start (substring checks aside).
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.