The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words return -1.
I tried finding the longest prefix and proceeding but that doesn't seem to work. I searched this question online and found a similar stack exchange question but I believe that the solution provided is wrong. It looks like this person is finding the longest suffix and proceeding but this approach doesn't work. Link to similar question
The reason this doesn't work is because: Suppose the dictionary is:{i,iiiiface,facebook,book} and input instance is 'iiiiifacebook'. The given solution would select 'facebook' and then continue to select 5 'i's' making a total of 6 words when infact the optimal solution is: (book,iiiiface,i) which is just 3 words. Please correct me if I'm wrong.
Please help me find the optimal (DP) solution to this problem.