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. Each word in dictionary_words can be used multiple times in the partitioning. Return True if such a partition exists, otherwise return False.
Example 1
Input: input_string=banana, dictionary_words=[ban, ana, a]
Output: True
Explanation: The string banana can be segmented as ban + ana.
Example 2
Input: input_string=abcdef, dictionary_words=[ab, abc, cd, def, abcd]
Output: True
Explanation: The string abcdef can be segmented as abc + def.
Example 3
Input: input_string=xyzabc, dictionary_words=[xy, z, ab, c]
Output: True
Explanation: The string xyzabc can be segmented as xy + z + ab + c.
Example 4
Input: input_string=helloworld, dictionary_words=[hello, world, hell, ow]
Output: True
Explanation: The string helloworld can be segmented as hello + world.
Example 5
Input: input_string=segment, dictionary_words=[seg, ment, men]
Output: True
Explanation: The string segment can be segmented as seg + ment.
Constraints
Case 1
Input: input_string='aaaaaaa', dictionary_words=['a','aa','aaa']
Expected: True
Case 2
Input: input_string='abcxyz', dictionary_words=['abc','xy','z']
Expected: True
Case 3
Input: input_string='testcase', dictionary_words=['test','case','tes','tca']
Expected: True
Case 4
Input: input_string='impossible', dictionary_words=['im','pos','sib','le']
Expected: False
Case 5
Input: input_string='openai', dictionary_words=['open','ai','pen','a']
Expected: True