string - Find the longest word in the dictionary such that it can be built from successively adding a single character to a previous word -

i found following question , decider share 1 of possible solutions.

question:

suppose given dictionary of words based on alphabet fixed number of characters. please write method / function find longest word in dictionary such can built successively adding single character existing word in dictionary (in location).

for instance, “a” -> “at” -> “cat” -> “chat” -> “chart”.

this great example of dynamic programming. dynammic programming section of book http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf . starts simple examples , builds complex ones in way makes lot of sense.

the challenge dp build solutions operate in polynomial time. dp solutions o(n^2), still better exponential (such trying every combination in dictionary). solution involve using arrays build information continue build on , lead answer