Word Break

Return True if s can be split into a sequence of one or more words from word_dict. A word may be used any number of times.

Example 1

Input: s = "leetcode", word_dict = ["leet", "code"]
Output: True

Example 2

Input: s = "applepenapple",
       word_dict = ["apple", "pen"]
Output: True
"apple" is used twice

Example 3

Input: s = "catsandog",
       word_dict = ["cats", "dog", "sand", "and", "cat"]
Output: False

Constraints

• 1 ≤ len(s) ≤ 300
• 1 ≤ len(word_dict) ≤ 1000, words are 1–20 letters
• lowercase letters only; the words are distinct