Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 1 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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