Practice: Word Break
Dynamic programming on strings.
Given a string with no spaces, and a dictionary of words, can the string be split into dictionary words? Apple pen apple can. Cats and og cannot. Pause. What smaller question would help?

- A string with no spaces
- A list of words
- Can it be split?
Can each prefix be split?
Let ok of I mean, the first I letters can be split into words. The empty prefix always can. For each end position, we look for a split point J, where the prefix up to J works, and the piece from J to I is a word. Run it. The first splits, and the second doesn't.
def word_break(s, words):
words = set(words)
ok = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for j in range(i):
if ok[j] and s[j:i] in words:
ok[i] = True
break
return ok[len(s)]
print(word_break("applepenapple", ["apple", "pen"]))
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))True False
The DP recipe again
This follows the same recipe as every dynamic programming problem. Define what each entry means, find the starting value, and write the rule that builds each answer from smaller ones. Here, there are O of N squared split points, and checking a set is quick.
| key | value |
|---|---|
| ok[i] | first i letters can split |
| Start | ok[0] = True |
| Rule | ok[j] and s[j:i] is a word |
| Answer | ok[len(s)] |
Summary
Word break asks whether each prefix can be split, building from shorter prefixes. It's dynamic programming on a string. Next, how long a message takes to reach a whole network.
Key takeaways- ok[i] for each prefix
- ok[0] is True
- Look for a split point