Problem. Given a string s and a dictionary of words, return whether s can be segmented into a space-separated sequence of
one or more dictionary words (words may be reused).
s = "leetcode", dict = ["leet", "code"] → True
s = "applepenapple", dict = ["apple", "pen"] → True
s = "catsandog", dict = ["cats", "dog", "sand", "and", "cat"] → False
Lesson 12.2 counted segmentations of a string into tokens. Here we ask whether any exists, and the state is the same: a prefix length i is "good" if some dictionary word ends at i and the prefix before that word is good.
ML context. Splitting text without spaces into known units is what subword tokenizers do for every word: a unigram tokenizer (SentencePiece) picks the most probable segmentation of each word into vocabulary pieces with exactly this DP using probabilities (Change C). It's also how Chinese and Japanese text, hashtags (#machinelearningrocks) and URLs are split into words.