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.