动态规划最小编辑距离python代码
如果是A串的第i个字符和B串的第j个字符1.在A的第i个字符后插入一个字符B[j],问题转化为计算A[i...lenA]和B[j+1...lenB]的距离2.删除A串的第i个字符,问题转化为计算A[i+1...lenA]和B[j...lenB]的距离3.将A的第i个字符替换成B的第j个字符,问题转化为计算A[i+1...lenA]和B[j+1...lenB]的距离。于是替换操作的编辑距离就是d[i-1][j-1]+flag。其中,当A[i]==B[j]时,flag=0,A[i]!=B[j],flag=1d[i-1][j]、d[i][j-1]、d[i-1][j-1]进行比较,其中最小的就是当前A和B的编辑距离
用户评论