本文主要是介绍最小编辑距离 | Minimum Edit Distance，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
设A、B为两个字符串，狭义的编辑距离定义为把A转换成B需要的最少删除（删除A中一个字符）、插入（在A中插入一个字符）和替换（把A中的某个字符替换成另一个字符）的次数，用ED（A，B）来表示。直观来说，两个串互相转换需要经过的步骤越多，差异越大。
对于编辑距离的状态转移较为难想。
正确的思路应当是将s1的前i位数据转换成s2的前j位数据所需要的转换步数设置为dp[i][j]
如上图，由上往下表示添加，例如a->azc
由左往右表示删除，例如abc->a
斜向下表示更新，例如abc->azc
于是某一点的最小编辑距离首先需要考虑的是s[i]==s2[j]??
如果相等，则考虑d[i][j]=dp[i-1][j-1];也即这一位不需要进行变换。
而不相等的时候，需要进行变换，并寻找如何才能在最短的步数完成变换。
故有3条方式：以ab->az为例
不考虑b的时候，a->az = 1，故ab->az = 2 ，也即在a->az基础上添加b
不考虑z的时候，ab->a = 1，故ab->az = 2 ， 也即在a->az基础上删除b，添加z，一共2步
不考虑b和z的时候，a->a = 0, 故ab-
这篇关于最小编辑距离 | Minimum Edit Distance的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
