All problems

Word Break

Medium · dynamic programming

You are given a string s and a list of words word_dict. Return true if s can be built by gluing dictionary words together with nothing in between, and false otherwise.

You may use the same word as many times as you like, and you must use up the whole string. Words that never appear in the split are simply ignored. The string is never empty.

Examples

Example 1

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

Output: True

"leet" followed by "code" spells the whole string.

Example 2

Input: s = "aaaaaaa", word_dict = ["aaaa", "aaa"]

Output: True

"aaaa" followed by "aaa" is exactly 7 letters.

Example 3

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

Output: False

You can spell "catsand" with "cats" + "and" (or "cat" + "sand"), but then "og" is left over and no word covers it.

Constraints

• 1 <= len(s) <= 300
• 1 <= len(word_dict) <= 1000
• 1 <= len(word_dict[i]) <= 20
• s and every word use lowercase English letters only.
• The dictionary may contain duplicate words.