Minimum words in a string given a dictionary 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.
One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

Example:- 

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)-&gt;f(boardrocks)
                -&gt;f(rocks)
                -&gt;f(s)


(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length m of the string in an array.

So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]