Segment Words

You're given a string with no spaces and a dictionary of allowed words. Decide whether the string can be cut into a sequence of one or more pieces where every piece is a word in the dictionary. Think of an old telegram or a URL slug like lostandfound — the same letters could read as lost and found or as nonsense, and you want to know whether any clean reading exists. This is the classic Word Break problem.

Signature

// s:    string — the text to segment (no spaces).
// dict: string[] | Set<string> — the allowed words.
// returns: boolean — true if s can be split into a
//   sequence of one or more dictionary words.
function stringSegmentWords(s, dict): boolean;

Each dictionary word may be used as many times as you like. The whole string must be consumed — a split that covers only a prefix does not count.

Examples

stringSegmentWords("applepenapple", ["apple", "pen"]);
// → true   ("apple" + "pen" + "apple"; "apple" is reused)

stringSegmentWords("catsandog", ["cats", "dog", "sand", "and", "cat"]);
// → false  (you can reach "cats" + "and" → "og" left over,
//           or "cat" + "sand" → "og" left over; no split finishes)

stringSegmentWords("leetcode", ["leet", "code"]);
// → true   ("leet" + "code")

Notes

• Words are reusable. A word in the dictionary can appear any number of times in the segmentation (see "applepenapple").
• The whole string must be consumed. Matching a prefix is not enough; the split has to reach the end of s with nothing left over.
• An empty string is segmentable. stringSegmentWords("", anything) returns true — the empty sequence of words trivially produces the empty string. This is the base case the algorithm leans on.
• The dictionary may arrive as an array or a Set. Accept either; internally a Set gives O(1) membership checks.
• Don't worry about returning the actual words, counting the number of valid segmentations, or punctuation/casing — s and the dictionary are plain lowercase letters.