Sentence Segmentation
Problem
Given a string with no spaces and a dictionary of words, decide whether the string can be cut into a sequence of dictionary words placed end to end. Words may be reused as often as needed, and every character must belong to exactly one word. Return true when such a cut exists.
Examples
Input: text = applepen, words = [apple, pen]
Output: True
Why: the cut apple + pen uses every characterInput: text = applepin, words = [apple, pen]
Output: False
Why: the tail pin is not a dictionary wordInput: text = "", words = [apple]
Output: True
Why: edge case, an empty string is already fully covered by zero wordsHints
0 / 3
Greedily taking the longest matching word fails, because an early choice can strand the rest of the string. Every cut point deserves consideration.
Ask a simpler question for each position: can the text up to here be covered completely? Answers for later positions depend only on answers for earlier ones.
Mark position zero as covered, then move an end marker along the string. For each end, look for any earlier covered position such that the piece between them is a dictionary word, and mark the end covered if one exists. The answer is whether the final position is covered.
Solution
A flag per position records whether the prefix ending there can be built entirely from dictionary words, with position zero true because the empty prefix needs nothing. Each position is confirmed by finding an earlier confirmed position whose following piece is a word, which reuses answers instead of re-exploring cuts. Storing the dictionary in a set keeps each piece lookup constant on average. Time is O(L squared) piece checks for a string of length L, and space is O(L) plus the dictionary.
def can_segment(text, words):
vocab = set(words)
covered = [False] * (len(text) + 1)
covered[0] = True # the empty prefix needs no words at all
for end in range(1, len(text) + 1):
for start in range(end):
# a cut works when the prefix is covered and the piece is a word
if covered[start] and text[start:end] in vocab:
covered[end] = True
break
return covered[-1]
print(can_segment("applepen", ["apple", "pen"])) # -> True
print(can_segment("applepin", ["apple", "pen"])) # -> False
print(can_segment("", ["apple"])) # -> TrueStuck on the idea rather than the code? Top-Down vs Bottom-Up covers it.