Dynamic Programming — Word Break

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

Trying every split recursively is exponential on inputs like
'aaaaaaaaab'. canBreak[i] (can the first i characters be split?) is
true when some j < i has canBreak[j] true and s.slice(j, i) is a
dictionary word. With the words in a set: O(n²) substring checks.

Examples

solve('leetcode', ['leet', 'code'])                     → true
solve('applepenapple', ['apple', 'pen'])                → true
solve('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']) → false

Constraints

• 1 <= s.length <= 300, 1 <= words.length <= 1000
• Lowercase letters only; the dictionary words are distinct.