Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

1 Answer 1

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

 
discard

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.