Word break: split a string into dictionary words

Given a string s and a list of dictionary words, return whether all of s can be split into a sequence of dictionary words. A word may be used any number of times, and every character of s must belong to exactly one chosen word. The empty string can always be split.

Interface

Unless you agree on a different interface with the interviewer, assume:

• word_break(s: str, words: list[str]) -> bool.

Example

s = "applepenapple", words = ["apple", "pen"]                       ->  True    # apple + pen + apple
s = "catsandog",     words = ["cats", "dog", "sand", "and", "cat"]  ->  False
s = "",              words = ["a"]                                  ->  True

Constraints

• 0 <= len(s) <= 10^4.
• Up to 5,000 non-empty lowercase words; duplicates in the list have no extra effect.

Clarifying questions

• Can words be reused?
• Is the empty string a valid input, and is it splittable?
• Do I need one actual split, all splits, or only yes or no?
• How long are the longest dictionary words?

What a strong answer covers

• Why greedy (always taking the longest or shortest matching word) fails, using catsandog or a similar example.
• The DP: ok[i] is true when the prefix of length i can be split; ok[0] is true, and ok[i] is true if some word ends at i and ok[i - len(word)] is true.
• Limiting the inner loop to the lengths that actually occur in the dictionary, giving O(n * L) substring checks for maximum word length L, each costing O(L).
• A trie walk from each reachable position, or BFS over positions, as alternatives.
• Tests: empty string, a single character, a string that needs a word reused many times, no possible split, a long string of as followed by b.

Follow-ups

• Return every possible split as sentences, and discuss the output size.
• Return the split that uses the fewest words.
• The dictionary is huge and shared, and many strings are checked. How do you organize it?