1

我的问题类似于通过有效单词将一个单词转换为另一个单词的算法

但有一个主要区别。我有一个固定的词说“詹姆斯”和不同的字典作为 i/p。当然，我现在不能预处理字典。

所以我必须找到用不同的字典作为输入处理“JAMES”到“JOHNY”的最低成本。

无论如何我可以预处理“JAMES”这个词，以便我需要在运行时执行最少数量的编辑距离计算？你们有什么建议？

4

2 回答 2

1

我假设规则与您引用的问题相似，即一次只允许进行一次编辑，并且每个中间词都应该出现在给定的字典中。

  1. 创建源字符串到目标字符串的单一编辑版本。例如：JOMES JAHES JAMNS JAMEY

对这些单词中的每一个进行递归，并为每个唯一单词继续创建节点。如果节点已经创建，只需创建边。这样就完成了预处理。

现在给定一个字典，找到字典中所有的第一级单词。对于所有匹配，进一步查找所有二级单词，依此类推，直到到达目标单词。

于 2012-07-28T17:08:39.877 回答
0

首先，您需要正确定义您的规则——“编辑”是否允许添加或删除多个字符、替换一个字符等？

无论如何-我只是从显而易见的开始-创建一个图表，其中每个单词都链接到可以直接编辑的所有单词。然后，使用具有深度限制的递归，将访问过的元素标记为“脏”以避免循环，然后查看是否存在一次编辑解决方案、二次编辑解决方案等，直到找到解决方案或所有路径在该深度都是脏的。（如果您在“脏”成员中记录尝试的深度，则不必担心每次增加深度限制时都会清除它们。您还可以标记所有脏子树以避免再次递归到它们.)

于 2012-04-24T02:16:13.253 回答