Word Break

Return True if the string s can be split into a sequence of words from words (words may be reused any number of times).

For s = "leetcode" and words = ["leet", "code"] the answer is True; for s = "catsandog" and words = ["cats", "dog", "sand", "and", "cat"] it is False.

The starter code tries every split without remembering failures. It is correct but too slow on strings that cannot be split.

Examples

Example 1

Input:

word_break('leetcode', ['leet', 'code'])

Output:

True

Example 2

Input:

word_break('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])

Output:

False

Constraints

• 0 <= len(s) <= 20000
• 0 <= len(words) <= 1000
• 1 <= len(word) <= 20, lower-case letters.