通过有效词将一个词转换为另一个词的算法

Question

我遇到了 edit-distance 的这个变体问题:

设计一个将源词转换为目标词的算法。例如:从头到尾，每一步只能替换一个字符，而且这个词必须是有效的。你会得到一本字典。

它显然是 edit distance 的变体问题，但在编辑距离上我不关心这个词是否有效。那么我该如何添加这个要求来编辑距离。

Answer 1

这可以建模为图形问题。您可以将单词视为图形的节点，当且仅当它们长度相同且只有一个字符不同时，两个节点才相连。

您可以预处理字典并创建此图，应该如下所示:

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

然后您可以将单词映射到表示单词的节点，为此您可以使用哈希表、高度平衡 BST ...

完成上述映射后，您要做的就是查看两个图节点之间是否存在路径，这可以使用 BFS 或 DFS 轻松完成。

因此您可以将算法总结为:

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