Word Break

Check whether a string can be split into dictionary words.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Word Break: Only reachable boundaries may launch dictionary words; each full prefix match adds its ending boundary.

Input and goalCheck whether a string can be split into dictionary words.

Initialize boundary 0The empty prefix is reachable, so reachable={0} before scanning any start.

start=0reachable0|0c1a2t3s4a5n6d7o8g9

exampletext = "catsandog", words = ["cats", "dog", "sand", "and", "cat"]positionMeaningboundary after index characters; cell 0 is empty prefixreachable{0}operationinitialize

Recognize it

The string must be segmented into reusable dictionary words, so each valid prefix endpoint can seed another exact prefix match.

Keep true

Before scanning start s, reachable contains exactly the boundaries proven segmentable using dictionary words from earlier starts; only members may create new endpoints.

Reuse it

Treat partial solutions as reachable boundaries and propagate only from proven states; this transfers to sentence segmentation, path reachability, and parsing with reusable tokens.

Pattern: DP over reachable string positions.

Simple idea: Position 0 is reachable before using any word. From each reachable position, try every dictionary word. A matching word makes its ending position reachable.

def word_break(text: str, words: list[str]) -> bool:
   reachable = {0}
   for start in range(len(text) + 1):
      if start not in reachable:
         continue
      for word in words:
         if text.startswith(word, start):
            reachable.add(start + len(word))
   return len(text) in reachable

Cost: $O(nwk)$ time and $O(n)$ space, where $w$ is the number of words and $k$ is the largest word length.