Word Break

The Idea

Walk the string left to right and ask one question per position: is this prefix splittable? It is, if some earlier splittable cut is followed by a word in the dictionary. The empty prefix is the base case. Greedy fails here — a long match early on can strand the tail — so every cut point gets tried.

Real-World Example

A search box splitting a typed domain like "codecamp" into words so it can suggest the right pages. Users drop the spaces; the index still needs them. One pass over the string with a dictionary set does the segmentation.

The Code

words = {"code", "camp", "cam"}
text = "codecamp"

ok = [False] * (len(text) + 1)
ok[0] = True                             # the empty prefix always splits
for i in range(1, len(text) + 1):
    for j in range(i):
        if ok[j] and text[j:i] in words:   # a valid cut, then a real word
            ok[i] = True
            break

print(ok)       # [True, False, False, False, True, False, False, True, True]
print(ok[-1])   # True — "code" + "camp"; the "cam" cut is a dead end

words = {"ab", "abc", "cd"}
text = "abcd"
ok = [False] * 5
ok[0] = True
for i in range(1, 5):
  for j in range(i):
      if ok[j] and text[j:i] in words:
          ok[i] = True
          break
print(ok)