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.