Algorithm Identification [ String & Dictionary ]

Question

I recently heard of an interview question:

 Given a string and a dictionary. Break the string into meaningful words

and I remember solving this before with dynamic programming fairly quickly (maybe O(n) time? ) in one of my old algorithm classes but I can not remember the name of the algorithm. Could someone point me in the right direction?

Answer 1

Your instincts are on the money though as suggested in this Stack Overflow question, tries (prefix trees) are also a valid solution. The process is called "Word Segmentation".