I came across this variation of edit-distance problem:
Design an algorithm which transforms a source word to a target word. for example: from head to tail, in each step, you just can replace one character, and the word must be valid. You'll be given a dictionary.
It clearly is a variation of the edit distance problem, but in edit distance I do not care about if the word is valid or not. So how do I add this requirement to edit distance.
See Question&Answers more detail:os