219. Word Break

Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words (words may be reused). Input: JSON {s, words}.

Input: JSON {s, words}.

Output: Boolean — true or false.

Examples

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

Input: {"s":"applepenapple","words":["apple","pen"]}
Output: true
Explanation: Reuse 'apple'.

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

Constraints

• 0<=s.length<=300
• 1<=words.length<=1000

Asked by