Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input:
leetcode
leet code
Output: true

Example 2:

Input:
applepenapple
apple pen
Output: true

Example 3:

Input:
catsandog
cats dog sand and cat
Output: false

Constraints:

• 1 ≤ s.length ≤ 300
• 1 ≤ wordDict.length ≤ 1000
• 1 ≤ wordDict[i].length ≤ 20

Input format: First line: string s. Second line: space-separated words in dictionary.

Output format: true or false.