通过每次迭代更改每个字母来将一个单词转换为另一个单词的算法，这应该形成另一个有意义的单词？
我想制作一种将一个单词更改为另一个单词的算法。例如，给定的单词是“MUD”，我需要将其转换为“BED”。对于每次迭代，我可以更改一个字符，但这应该形成另一个有意义的单词。例如“MUD”可以更改为“MAD”。像这样我需要找到将“MUD”转换为“BED”的最短路径。
提供了一种单独的方法来查找有效单词。 IsWord() 是一种方法，它将为我们提供布尔结果，无论给定的字符串是否有效。所以不用担心这个。
我也不需要担心效率或代码行等。有人知道如何制作这个算法吗？如果是这样，请帮助我。
提前致谢。
（我知道我们必须使用树并且必须进行二元遍历，但我不知道如何在这个算法中使用它）
I want to make an algorithm for changing one word to other. For example the given word is "MUD" and I need to convert it to "BED". For each iteration I can change one character, but that should form an another meaningful word. For example "MUD" can be change as "MAD". Like this I need to find the shortest path to convert the "MUD" to "BED".
A separate method is provided for finding the valid word. IsWord() is a method which will give us the boolean result whether the given string is valid or not. So dont need to worry about that.
I also dont need to worry about efficiency or lines of code , etc. Do any one have any idea how to make this algorithm. If so please help me.
Thanks in Advance.
(I know that we have to use tree and have to do binary traversal, but I have no idea how to use it in this algorithm)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这称为词梯。
查看帖子有史以来最长的单词梯谜题Wolfram 博客上的 。
This is called a word ladder.
Check out the post The Longest Word Ladder Puzzle Ever on Wolfram Blog.
首先有一个包含元素（字符串）的排序队列。
每个元素都有一个到目标词的评级/距离（根据启发式）。这可以是汉明距离。排序队列使用这个距离将最接近目标的单词推到顶部。
您取出第一个单词，将其添加到队列中。从队列中提取第一个元素，展开其所有子元素（可以通过单个转换从中获取的单词）并将它们放入队列中。执行此操作，直到从队列中获取的元素就是您要搜索的元素或队列为空。
You start by having a sorted queue with elements (strings).
Each element has a rating/distance (according to an heuristic) to the target word. This can be a Hamming Distance. And the sorted queue uses this distance to push on top the word closest to the target.
You take your first word, add it to the queue. Extract from the queue the first element, expand all of its children (words that can be obtained from it through a single conversion) and put them in the queue. Do this until the element you get from the queue is the one you are searching for or the queue is empty.
按以下方式创建图表：
每个单词都是一个节点，如果您可以一步从一个单词转到另一个单词，则两个节点相连。
现在找到原始单词和最终单词之间的最短距离和路径。
请参阅：http://en.wikipedia.org/wiki/Shortest_path_problem 了解如何计算最短路径。
Create a graph the following way:
Each word is a node and two nodes are connected if you can go from one word to another in one step.
Now find the shortest distance and path between original word and final word.
See: http://en.wikipedia.org/wiki/Shortest_path_problem on how to calculate shortest path.
在每次迭代中，将所有可能的新单词组成您拥有的单词，并将它们收集在列表、集合或其他形式中。过滤掉以前已有的重复项和单词。例如：
您要么最终得到一个空列表，则问题无法解决，或者所查找的单词在列表中。
In each iteration, make all possible new words form the words you have and collect them in a list, set or whatever. Filter out duplicates and words you already had before. For example:
You either end up with an empty list, then the problem is not solvable, or the sought word is in the list.