编辑距离C/C++实现
编辑距离的动态规划实现,C/C++,直接可以使用,设:A字符串为a[0:m-1],B字符串为b[0:n-1]; d[i][j]表示a[0]到a[i]变化为b[0]b[j]的编辑距离; 则有: {█(d[i][j]=d[i-1]d[j-1],a[i]=b[j]@min┬█(0≤i≤m-1,@0≤j≤n-1)〖{d[i-1][j],d[i][j-1],d[i-1][j-1]}+1, a[i]1=b[j]〗 )┤ 算法的时间复杂度:T(m,n)=O(mn)
用户评论