我遇到了编辑距离问题的这种变体：
找到从一个单词到另一个单词的最短路径，例如storm->power，使用 isValidWord() 函数验证每个中间单词。没有其他方式可以访问单词词典，因此无法构建图表。
我正在尝试解决这个问题，但这本身似乎并不是与距离相关的问题。也许使用简单的递归？但你怎么知道你的方向是正确的呢？
还有人觉得这很有趣吗？期待一些帮助，谢谢！
I came across this variation of edit-distance problem:
Find the shortest path from one word to another, for example storm->power, validating each intermediate word by using a isValidWord() function. There is no other access to the dictionary of words and therefore a graph cannot be constructed.
I am trying to figure this out but it doesn't seem to be a distance related problem, per se. Use simple recursion maybe? But then how do you know that you're going the right direction?
Anyone else find this interesting? Looking forward to some help, thanks!
发布评论
评论（2）
这是刘易斯·卡罗尔 (Lewis Carroll) 设计的一个谜题，称为Word Ladders。 Donald Knuth 在 Stanford Graphbase 中介绍了这一点。这也
可以将其视为广度优先搜索。您将需要访问单词词典，否则您需要搜索的空间将会很大。如果您只能访问有效单词，则可以生成单词的所有排列，然后只需使用 isValidWord() 对其进行过滤（Norvig 的“How to Write a Spelling Corrector" 是生成编辑的一个很好的解释）。
您可以通过尝试最小化当前所在位置与未来位置之间的编辑距离来引导搜索。例如，生成所有节点的空间进行搜索，并按最小编辑距离排序。首先遵循距离目标最近的链接（例如，最小化编辑距离）。在示例中，遵循最接近“power”的节点。
我发现这也很有趣，所以这里有一个 Haskell 实现效果相当好。评论中有一个链接 Clojure 版本，它有一些非常好的可视化效果。
This is a puzzle from Lewis Carroll known as Word Ladders. Donald Knuth covers this in The Stanford Graphbase. This also
You can view it as a breadth first search. You will need access to a dictionary of words, otherwise the space you will have to search will be huge. If you just have access to a valid word you can generate all the permutations of words and then just use isValidWord() to filter it down (Norvig's "How to Write a Spelling Corrector" is a great explanation of generating the edits).
You can guide the search by trying to minimize the edit distance between where you currently are and where you can to be. For example, generate the space of all nodes to search, and sort by minimum edit distance. Follow the links first that are closest (e.g. minimize the edit distance) to the target. In the example, follow the nodes that are closest to "power".
I found this interesting as well, so there's a Haskell implementation here which works reasonably well. There's a link in the comments to a Clojure version which has some really nice visualizations.
您可以同时从两侧进行搜索。即在storm中改变一个字母，通过isValidWord()运行，在power中改变一个字母，通过isValidWord()运行。如果这两个词相同，那么你就找到了一条路。
You can search from two sides at the same time. I.e. change a letter in storm and run it through isValidWord(), and change a letter in power and run it through isValidWord(). If those two words are the same, you have found a path.