Word Break

Return true if s can be split into words from wordDict. A word may be used many times.

Examples

Example 1

Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true

Example 2

Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true