How to find number of words in a phrase with spaces removed by checking v. dictionary

You can use Dynamic Programming for this task:

f(0) = 0
f(i) = MIN { f(i-j) + (Dictionary.contais(s.substring(i-j,i)?1:INFINITY } for each j=1,...,i

The above finds the number of words in your string, so the final answer is f(#characters)-1

The idea is to do an “exhaustive search” – for a given new character – try to connect it to a word, and recursively invoke on what’s left from the string.

This can be done pretty efficiently with DP techniques.

Browse More Popular Posts

Leave a Comment