How do you solve the word break problem?

Question presented to candidate: "Given a string and a dictionary of words, decide whether the string can be split into a sequence of one or more dictionary words, using any word as many times as you like. For example, 'applepenapple' with the words 'apple' and 'pen' is true. Explain the approach and code it in Python."

What a strong answer should cover:

• The state: ok[i] is true when the first i characters can be split into words, with ok[0] = true for the empty prefix.
• The transition: ok[i] is true if some j < i has ok[j] true and s[j:i] in the dictionary; put the words in a hash set first, and stop at the first j that works.
• Complexity: O(n²) substring checks (each costing up to O(n) to build and hash), reduced to O(n · L) checks when j only goes back as far as the longest word length L.
• Why plain recursion explodes (a string of as ending in b, with words a, aa, aaa…) and how memoization on the start index fixes it; how to rebuild one split by remembering where the last word starts.
• Python details: set(words) for O(1) average lookups, that s[j:i] builds a new string each time, and max((len(w) for w in words), default=0) for an empty dictionary.

Clarifying questions expected:

• Can dictionary words be reused, and is the empty string considered breakable?
• How long are the string and the words — is the dictionary large?
• Do you need just true/false, one split, or all possible splits?

Code / implementation expected: Yes — a bottom-up Python DP over prefix lengths with a hash set; rebuilding one split is a common follow-up.