Interview challenge · medium · string, dynamic-programming, hash-set
Word Break
The challenge
Given a string s and a list of words, return true if s can be cut into a sequence of one or more words from the list. The same word can be used as many times as you want.
Example
words: cat, cats, and, sand, dog
"catsanddog" -> true (cats + and + dog, or cat + sand + dog)
"catsandog" -> false ("og" is left over either way)Idea: dynamic programming over prefixes. ok[i] says whether the first i characters can be cut into words. The empty prefix always can, so ok[0] is true. A longer prefix s[:i] works if some shorter good prefix s[:j] is followed by a word, s[j:i]. Fill the table from left to right and read the last cell. With the words in a hash set that is O(n²) lookups for a string of length n (each one hashes a slice), and O(n) space.
The solution
# Word Break - ayotl.dev
def word_break(s, words):
# ok[i]: s[:i] splits into words
ok = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for j in range(i):
# a good prefix + one word
if ok[j] and s[j:i] in words:
ok[i] = True
break
return ok[len(s)]
words = {"cat", "cats", "and",
"sand", "dog"}
for s in ["catsanddog", "catsandog"]:
ok = word_break(s, words)
print(s, "true" if ok else "false")
$ python3 word_break.py
catsanddog true
catsandog false