我遇到了这种编辑距离问题的变体：
设计一种将源词转换为目标词的算法。例如：从头到尾，在每个步骤中，您只能替换一个字符，并且该单词必须有效。您将得到一本字典。
显然这是编辑距离问题的一种变体，但是在编辑距离中，我并不关心单词是否有效。因此，如何添加此要求以编辑距离。
可以将其建模为图问题。您可以将单词视为图的节点，并且当且仅当它们的长度相同且一个字符不同时，两个节点才被连接。
您可以预处理字典并创建此图，如下所示：
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
