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

Question

我遇到了编辑距离问题的这种变化:

设计一种将源字转换为目标字的算法.例如:从头到尾,在每一步中,你只需要替换一个字符,并且该字必须有效.你会得到一本字典.

它显然是编辑距离问题的变体,但在编辑距离中我不关心该单词是否有效.那么如何添加此要求来编辑距离.

Answer 1

这可以建模为图形问题.您可以将这些单词视为图形的节点,并且当且仅当它们具有相同的长度并且在一个char中不同时,才连接两个节点.

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

   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

Answer 2

codaddict的图方法是有效的,尽管构建每个图需要O(n ^ 2)时间,其中n是给定长度的字数.如果这是一个问题,您可以更有效地构建一个bk树,这样就可以找到目标字的给定编辑距离(在本例中为1)的所有单词.