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

Question

我相信你们都听说过"文字游戏",你试图通过一次改变一个字母来改变一个单词到另一个单词,并且只通过有效的英语单词.我正在尝试实现一个A*算法来解决它(只是为了充实我对A*的理解),其中一个需要的是最小距离启发式.

也就是说,这三个突变中的一个可以将任意字符串变成另一个字符串b的最小数量b:1)将一个字母改为另一个字母2)在任何字母之前或之后的某个地方添加一个字母3)删除任何字母

例子

aabca => abaca:
aabca
abca
abaca
= 2

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

我尝试了很多算法; 我似乎无法找到每次给出实际答案的人.事实上,有时我甚至不确定我的人类推理是否找到了最佳答案.

有没有人为此目的知道任何算法？或者也许可以帮我找到一个？

(只是为了澄清,我要求的算法可以将任意字符串转换为任何其他字符串,无视其英语有效性.)

Answer 1

您想要最小编辑距离(或Levenshtein距离):

两个字符串之间的Levenshtein距离定义为将一个字符串转换为另一个字符串所需的最小编辑数,允许的编辑操作是单个字符的插入,删除或替换.它以弗拉基米尔·莱文施泰因(Vladimir Levenshtein)的名字命名,他在1965年考虑过这个距离.

确定编辑序列的一种算法在此处在同一页面上.