algorithm - 将一个字符串转换为另一个字符串

Question

这是一道面试题。我需要将字符串 a 转换为 b 以便一次只更改一个字母，并且在每次更改后，转换后的字符串都在字典中。您需要以最少的转换次数执行此操作。例如从 cat-->boy 的转换可以如下进行：

 cat-->bat-->bot-->boy (if dictionary has bat and bot)

我可以考虑为这个问题创建一个前缀树（trie），但我不确定一旦我有一个 trie 如何继续。有人可以建议一种可能的方法吗？我试图避免使用蛮力方法。

Answer 1

如果您想知道计算单个字符编辑的最小数量，请查看Levenshtein distance。但是，这假定只允许插入、删除和替换。

对于您的示例，更改 cat -> boy 的 Levenshtein 距离为 3，具有三个替换（c->b、a->o、t->y）。

如果还允许换位，那么您应该考虑Damerau-Levenshtein 距离。

例如，cat -> cta 的 Levenshtein 距离为 2，而 Damerau-Levenshtein 距离为 1

Answer 2

您已经将问题分解为前缀树。

要找到解决方案，还需要采取更多步骤：

1. 编写一个函数，该函数接受输入字符串并通过查询 trie-dictionary 查找可能的转换。
2. 提出一个可接受的启发式方法，您可以使用它在结果之间进行选择。
3. 使用众所周知的最短路径算法，例如A* 搜索算法。