Determine Whether a String Can Be Segmented into Dictionary Words

## Problem Given a string and a set of words, return whether the entire string can be formed by concatenating dictionary words. A dictionary word may be reused any number of times. Every character of the input string must belong to exactly one chosen segment. ### Constraints & Assumptions - The string length is at most 10,000. - The dictionary contains at most 5,000 non-empty lowercase words. - Duplicate dictionary entries have no additional effect. - The empty input string is segmentable. ### Clarifications - The function returns a boolean and does not need to enumerate segmentations. - Words may overlap as candidates, but selected segments cannot overlap. - The same word can appear in multiple positions. ### Examples ```text s = "applepenapple", words = ["apple", "pen"] output = true s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"] output = false ``` ### Hints ```hint Choose a state boundary Track which prefixes are fully constructible rather than committing greedily to the longest word. ``` ```hint Limit candidate lengths The longest dictionary word can bound how far back each transition must inspect. ```