Given a string and a dictionary of words, the machine must decide whether the string can be segmented into a sequence of dictionary words. Words can be reused, and every character must belong to exactly one segment.
The key insight is that segmentation is prefix-composable: the whole string is segmentable exactly when some prefix is segmentable and the remaining suffix is a dictionary word. Greedy left-to-right matching fails here — the machine needs to remember every reachable boundary.
The approach runs in three steps. First, build a boolean array dp where dp[i] means the prefix ending at index i is segmentable, and set dp[0] = true. Second, for each ending index, check every earlier starting index: if dp[j] holds and s[j:i] is in the dictionary, mark dp[i] as true and stop scanning. Third, return dp[n]. Time is O(n^2) with O(n) substring checks and space is O(n).
The trickiest edge case is the false-friend dictionary, like "catsandog" with : a greedy matcher takes "cats" then gets stuck, but "cat","sand" also fails at "og". Only the full dp table proves no segmentation exists, because every boundary must be tried.
def wordBreak(s, wordDict):
words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]