Levenshtein distance，中文名为最小编辑距离，其目的是找出两个字符串之间需要改动多少个字符后变成一致。该算法使用了动态规划的算法策略，该问题具备最优子结构，最小编辑距离包含子最小编辑距离，有下列的公式。
其中d[i-1,j]+1代表字符串s2插入一个字母，d[i,j-1]+1代表字符串s1删除一个字母，然后当xi=yj时，不需要代价，所以和上一步d[i-1,j-1]代价相同，否则+1，接着d[i,j]是以上三者中最小的一项。
算法实现（Python）：
假设两个字符串分别为s1，s2，其长度分别为m，n，首先申请一个（m+1）*（n+1）大小的矩阵，然后将第一行和第一列初始化，d[i,0]=i，d[0,j]=j，接着就按照公式求出矩阵中其他元素，结束后，两个字符串之间的编辑距离就是d[n,m]的值，代码如下：
[python]view plaincopyprint?#!/usr/bin/envpython #-*-coding:utf-8-*- __author__='xanxus' s1,s2=raw_input('String1:'),raw_input('String2:') m,n=len(s1),len(s2) colsize,matrix=m+1,[] foriinrange((m+1)*(n+1)): matrix.append(0) foriinrange(colsize): matrix[i]=i foriinrange(n+1): matrix[i*colsize]=i foriinrange(n+1)[1:n+1]: forjinrange(m+1)[1:m+1]: cost=0 ifs1[j-1]==s2[i-1]: cost=0 else: cost=1 minValue=matrix[(i-1)*colsize+j]+1 ifminValue>matrix[i*colsize+j-1]+1: minValue=matrix[i*colsize+j-1]+1 ifminValue>matrix[(i-1)*colsize+j-1]+cost: minValue=matrix[(i-1)*colsize+j-1]+cost matrix[i*colsize+j]=minValue printmatrix[n*colsize+m]
