algorithm - 将一个字符串更改为另一个字符串的简单突变的数量？

Question

我相信你们都听说过“文字游戏”，在这个游戏中，您尝试通过一次更改一个字母来将一个词更改为另一个词，并且只通过有效的英文单词。我正在尝试实现 A* 算法来解决它(只是为了充实我对 A* 的理解)，其中需要的事情之一是最小距离启发式。

也就是这三个突变之一可以将任意字符串a变成另一个字符串b的最小数量:1) 将一个字母换成另一个2)在任何字母之前或之后的位置添加一个字母3) 删除任何字母

例子

aabca => abaca:
aabca
abca
abaca
= 2

abcdebf => bgabf:
abcdebf
bcdebf
bcdbf
bgdbf
bgabf
= 4

我已经尝试了很多算法；我似乎找不到每次都能给出实际答案的答案。事实上，有时我不确定我的人类推理是否找到了最佳答案。

有人知道用于此目的的算法吗？或者也许可以帮我找到一个？

(澄清一下，我要求的是一种算法，可以将任意字符串转换为任何其他字符串，而不管它们的英语有效性如何。)

Answer 1

你想要 minimum edit distance (or Levenshtein distance) :

The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965.

确定编辑顺序的一种算法在同一页上here .