Loading problem...
You are given a string s and a list of valid tokens called dictionary. Your task is to determine whether it is possible to partition the string s into one or more consecutive substrings, where each substring is a valid token present in the dictionary.
The partitioning must cover the entire string from start to end, with no characters left over and no gaps between substrings. Each token from the dictionary can be used multiple times in the segmentation if needed.
Return true if such a valid segmentation exists, and false otherwise.
s = "leetcode"
dictionary = ["leet","code"]trueThe string "leetcode" can be successfully partitioned into "leet" + "code". Both "leet" and "code" are valid tokens in the dictionary, and together they form the complete original string.
s = "applepenapple"
dictionary = ["apple","pen"]trueThe string can be segmented as "apple" + "pen" + "apple". Notice that the token "apple" is reused twice, which is allowed. The three segments concatenate to form the original string.
s = "catsandog"
dictionary = ["cats","dog","sand","and","cat"]falseAlthough we can segment the beginning of the string (e.g., "cats" + "and"), there is no valid way to segment the entire string. The remaining "og" cannot be matched to any dictionary token, making complete segmentation impossible.
Constraints