765. Word Break (Recursive + Memoization)

Given a string s and a dictionary of strings words, return true if s can be segmented into a sequence of one or more dictionary words. The same word may be reused any number of times. Implement with recursion + memoization. The input is provided as a JSON object with fields s (the string) and words (a list of strings).

Input: A JSON object: {"s": "...", "words": ["...", ...]}.

Output: Return a boolean: true or false (lowercase).

Examples

Input: {"s":"leetcode","words":["leet","code"]}
Output: true
Explanation: 'leet' + 'code' covers the whole string.

Input: {"s":"applepenapple","words":["apple","pen"]}
Output: true
Explanation: Words can be reused.

Input: {"s":"catsandog","words":["cats","dog","sand","and","cat"]}
Output: false
Explanation: No segmentation covers the whole string.

Constraints

• 0 <= s.length <= 30
• 1 <= words.length <= 20
• 1 <= words[i].length <= 20
• All strings consist of lowercase English letters

Asked by