I recently heard of an interview question: Given a string and a dictionary. Break the string into meaningful wordsand 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?
Algorithm Identification [ String & Dictionary ]
algorithms;strings
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.