String Segmentation

Medium

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.

Example 1

Input

s = "onenoughtone"
dictionary = ["one","nought"]

Output

true

Explanation

The string "onenoughtone" can be segmented as "one" + "nought" + "one". Each segment is a valid dictionary token, and the token "one" can be reused.

Example 2

Input

s = "applepenapple"
dictionary = ["apple","pen"]

Output

true

Explanation

The 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.

Example 3

Input

s = "catsandog"
dictionary = ["cats","dog","sand","and","cat"]

Output

false

Explanation

Although 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

1 ≤ s.length ≤ 300
1 ≤ dictionary.length ≤ 1000
1 ≤ dictionary[i].length ≤ 20
s and all dictionary tokens consist of only lowercase English letters.
All tokens in the dictionary are unique.