[jimmaswell]

>Given two words in a dictionary, transform one word into another using only words in the dictionary.

What's that supposed to mean? Search the dictionary for other words that contain the letters you want and put them into the source word, while also taking out unwanted letters from the source word?

[_nt_]

It indeed is interesting question. The solution which comes first to mind is creating a graph, with words as vertices, edges will be only if two words have a difference of single character. Once this graph is created, it's matter of running shortest path algo between two vertices. However, creating the graph itself could be a bitch, depending on size of dictionary.

[stevebot]

You have the additional requirement that you change one character at a time, and end up building a graph of neighbors and doing BFS on it.

[bmelton]

I've never heard this question before, but I assume it's finding words with the lowest Levenshtein distance between wordA and wordB and then wayfinding the route from wordA to WordB using the least steps possible?

[stevebot]

correct, I think it is actually a good interview problem for discussion and don't mind it. What I do mind is the attitude of some of my colleagues that if a candidate can't immediately jump to the optimal answer, then they are a pass.

[chenglou]

Can you englihten me on how edit distance helps here? I don't see why insert/remove/move is relevant in this case.

[bmelton]

Sounds like something I'd likely fail. Without putting pen to paper, I can get from taking the two words and expanding Lev distances until we find a word in common, and then mapping a a route from A to that word, then from that word to B, but whatever I wrote would probably be horribly inefficient, at best.

I would also wager that whomever was asking that sort of question would probably be looking for some optimal form of the answer, and having never encountered it, oh well.