Given an input string s and a dictionary of words wordDict, write a program to determine if s can be divided into a space-separated sequence of one or more words that are present in the wordDict.

Problem Note

• Assume that both s and wordDict are non-empty.
• The same word in the dictionary may be reused multiple times in the division.
• You may assume the dictionary does not contain duplicate words.

Example 1

Input: s = "AfterAcademy", wordDict = ["After", "Academy"]
Output: true
Explanation: Return true because "AfterAcademy" can be segmented as "After Academy".

Example 2

Input: s = "HardThingAboutHardThings", wordDict = ["Hard", "Things", "Thing", "About"]
Output: true
Explanation: Return true because "HardThingAboutHardThings" can be segmented as "Hard Thing About Hard Things". Note that you are allowed to reuse a dictionary word.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Explanation: All the words from the dictionary cannot be formed from the s.