我碰到这个变化编辑距离的问题：

设计一个算法，它可以将一个源字为目标字。例如：从头部到尾部，在每一个步骤，你只可以替换一个字符，而这个词必须是有效的。你会得到一本字典。

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.

这显然是的edit距离问题，但在编辑距离我不关心，如果这个词是有效还是无效。那么，如何增加这个要求编辑距离。

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.

推荐答案

这可以看作是一个图的问题。你能想到的词作为图的节点，当且仅当它们是相同的长度和不同的一个字符两个节点连接起来。

This can be modelled as a graph problem. You can think of the words as nodes of the graph and two nodes are connected if and only if they are of same length and differ in one char.

您可以preprocess字典创建此图，应该是这样的：

You can preprocess the dictionary and create this graph, should look like:

   stack  jack
    |      |
    |      |
   smack  back -- pack -- pick

您就可以拥有从单词到节点重新presenting字的映射，为此，你可以使用一个哈希表，高度平衡BST ...

You can then have a mapping from the word to the node representing the word, for this you can use a hash table, height balanced BST ...

在你在的地方上面的映射，所有你需要做的就是看是否存在在两个图的节点之间的路径，它可以很容易地使用BFS或DFS完成。

Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS or DFS.

所以，你可以概括算法：

So you can summarize the algorithm as:

preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
 Not possible to convert
else
 n1 = get_node(w1)
 n2 = get_node(w2)

 if(path_exists(n1,n2))
   Possible and nodes in the path represent intermediary words
 else
   Not possible