Medium · Prefix DP
Understand → Visualise → Practice.
Return whether the entire text can be segmented into one or more dictionary words; dictionary words may be reused.
possible[i] says whether text[:i] can be split into dictionary words. It is true if some earlier breakable point j leaves text[j:i] in the dictionary.
possible[0] = True: the empty prefix needs no words.
For each end i, set possible[i] if any start j has possible[j] and text[j:i] in the word set.
Return possible[len(text)].
O(n²) substring checks and O(n + dictionary size) space.
Greedily taking the longest available word can block a valid later segmentation.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.