find the longest word in a list made of other words in the list

From Cracking the Coding Interview.

This solution is not complete, but it solves a useful subset of inputs and does it correctly. Getting a working solution for a subset of posisble inputs is better than an incomplete or flawed solution that tries to cover all possible cases, as long as you can demonstrate to your interviewer that you understand the shortcomings of your solution.

This solution stops searching for a word when the smallest combination of characters in the compound word exists in the list. Therefor it will correctly return "peanut" for { "pea", "nut", "peanut" } but fail on { "pea", "peanut", "peanutbutter" } because it will break up "peanutbutter" after "pea" and not find a match for "nutbutter". A recursive solution that backtracks if it gets to the end of the string could solve this problem.

In C#:


Leave a comment -


I'm a .NET, PHP, Python, and Javascript developer. Also Project Manager, Scrum Master, and Juilliard trained violist. You cannot connect with me on Facebook, Twitter, or LinkedIn so don't ask.