Write word_break(s, words) -> bool: can s be cut into consecutive pieces so that every piece is in words? A dictionary word may be used any number of times.
word_break("sunflower", ["sun", "flow", "flower", "er"]) # True ("sun" + "flower")
word_break("seesaws", ["see", "saw", "sees"]) # False (no way to use the final "s")
word_break("", ["a"]) # True (zero pieces)
Constraints: len(s) <= 300, up to 1000 words of length 1..20, lowercase letters.
Plain recursion that tries every split re-solves the same suffix over and over and blows up exponentially on inputs like "aaaa...ab". Aim for roughly O(len(s) · longest word).
Show hint
Whether the rest of s can be segmented depends only on where you are in s, so remember the answer for each position. A set of the words (or a trie, to stop early when no word continues) finds the pieces that can start at a position.