Given a string input_string and a list of unique strings dictionary_words, determine if input_string can be partitioned into a sequence of one or more words from dictionary_words. Words from dictionary_words may be reused multiple times in the partitioning.
Example 1
Input: input_string=bananaapple, dictionary_words=[banana,apple]
Output: True
Explanation: bananaapple can be segmented as banana apple.
Example 2
Input: input_string=pineapplepen, dictionary_words=[pine,apple,pen]
Output: True
Explanation: pineapplepen can be segmented as pine apple pen.
Example 3
Input: input_string=orangejuice, dictionary_words=[orange,juice,ju]
Output: True
Explanation: orangejuice can be segmented as orange juice.
Example 4
Input: input_string=grapefruit, dictionary_words=[grape,fruit,apple]
Output: True
Explanation: grapefruit can be segmented as grape fruit.
Example 5
Input: input_string=watermelon, dictionary_words=[water,melon,lemon]
Output: True
Explanation: watermelon can be segmented as water melon.
Constraints
Case 1
Input: input_string='strawberryjam', dictionary_words=['straw','berry','jam']
Expected: True
Case 2
Input: input_string='blueberrypie', dictionary_words=['blue','berry','pie','apple']
Expected: True
Case 3
Input: input_string='chocolatecake', dictionary_words=['choco','late','cake']
Expected: False
Case 4
Input: input_string='mangopineapple', dictionary_words=['mango','pine','apple','banana']
Expected: True
Case 5
Input: input_string='kiwifruit', dictionary_words=['kiwi','fruit','grape']
Expected: True