AI Hints
Home›DSA in Python Tutorial›Windows, Words and Networks
DSA in Python · Lesson 116 of 132

Practice: Word Break

Dynamic programming on strings.

⏱ 2 min read▶ Video at 2:18:21🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Word Break
From the video: Practice: Word Break
  • 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.

word_break.pypython
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"]))
Output
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.

keyvalue
ok[i]first i letters can split
Startok[0] = True
Ruleok[j] and s[j:i] is a word
Answerok[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
Next up: Practice: Network Delay — Dijkstra in action