Given an input string S and a dictionary of words Dict, write a program to determine if S can be segmented into a space-separated sequence of one or more dictionary words.

Problem Note

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

Example 1

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

Example 2

Input: S = "HardThingAboutHardThings", Dict = ["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", Dict = ["cats", "dog", "sand", "and", "cat"]
Output: false