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?

1 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".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.