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?
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”.