Editor

Word Break

#115 · Dynamic programming · Intermediate · 90 XP · about 18 min

text is a string of lowercase letters written without spaces, and words is a list of allowed words. Write can_split(text, words) that returns True if you can cut text into pieces so that every piece is an allowed word, and False otherwise.

Each allowed word can be used any number of times. An empty text needs no pieces, so it counts as True.

Examples

can_split("icecream", ["ice", "cream", "am"])        # returns True
can_split("carpets", ["car", "pet", "carp", "ets"])  # returns True
can_split("goaltender", ["goal", "tend", "end"])     # returns False

"carpets" splits as "carp" + "ets", even though starting with "car" leads nowhere.

Constraints

  • 0 <= len(text) <= 300
  • 1 <= len(words) <= 1000
  • Each word has 1 to 20 lowercase letters

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.