Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
每组用例一共2行，为输入的两个字符串
每组用例输出一行，代表字符串的距离
abcdefg abcdef
1
这种一维压缩的方式真的妙啊
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
string str1,str2;
while(cin>>str1>>str2){
int m =str1.size();
int n = str2.size();
vector<int> dp(n+1,0);
for(int i =0;i<n+1;i++){
dp[i]=i;//这里初始化第一行很难理解，我们把dp里的二维给压缩成了一维
//二维保存了很多信息,但其实我们只需要最后一行的信息。
}
int diffi,diffj,diffij;
for(int i =1;i<m+1;i++){//这里开始第二行了，先把第二行第一列给赋值覆盖掉
//第一行之前赋的值，准备更新第二行的值了，这个外层就负责更新每一行的第一列
dp[0]=i;
diffij = dp[0]-1;//这里其实就是求dp[i][0]的上面一个因为列数为0上面一个dp
//值肯定要-1这个值后面的内层循环列的时候要更新
for(int j =1;j<n+1;j++){
diffj=dp[j];//如果想象成二维的话这里对应着i-1行的j列,就是以前的值我们
//我们要保留下来，因为后面列还要靠它来更新.//下面这里一定注意str1[i-1]
//我这用两种方法每次都搞错这里，i-1才表示前i个字符
dp[j]=min(dp[j]+1,min(dp[j-1]+1,((str1[i-1]==str2[j-1])?0:1)+diffij));
//上面这行min里的dp[j-1]之前已经更新过了的，min里的dp[j]其实是i-1行的j列,也就是没有
//覆盖掉的，等号左边就是即将更新的，他在这个内层循环的下一次又充当min里的dp[j-1]
diffij = diffj;//这里更新左上角的值，就是内层循环第一句那里为什么要保留了
}
}
cout<<dp[n]<<endl;//最后的dp[n]其实已经遍历m行了，只保留了最后一行
//这种方法空间复杂度就比较低
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.next();
String str2 = sc.next();
System.out.println(distanceString(str1, str2));
}
}
public static int distanceString(String str1, String str2) {
int len1 = str1.length(), len2 = str2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
// 初始化
int i = 0, j = 0;
for (i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (j = 0; j <= len2; j++) {
dp[0][j] = j;
}
// 动态规划，循环设置值
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = minNum(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[len1][len2];
}
public static int minNum(int num1, int num2, int num3) {
int temp = num1 < num2 ? num1 : num2;
return temp < num3 ? temp : num3;
}
} 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
int minDistance(string &s1, string &s2){
int len1 = s1.size(), len2 = s2.size();
if(len1 * len2 == 0)
return 0;
vector<int> dp(len2 + 1, 0);
for(int i = 0, left_up; i < len1 + 1; ++i){
for(int j = 0; j < len2 + 1; ++j){
if(0 == i) dp[j] = j;
else if(0 == j){
left_up = dp[j];
++dp[j];
}else{
if(s1[i - 1] != s2[j - 1]) ++left_up;
left_up = min(min(left_up, dp[j - 1] + 1), dp[j] + 1);
swap(left_up, dp[j]);
}
}
}
return dp[len2];
}
};
int main(){
Solution sol;
string s1, s2;
while(getline(cin, s1) && getline(cin, s2))
cout << sol.minDistance(s1, s2) << endl;
return 0;
} 上面是用一维动态数组。下面是是对应二维动态数组版本的。#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
int minDistance(string &s1, string &s2){
int len1 = s1.size(), len2 = s2.size();
if(len1 * len2 == 0)
return 0;
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for(int i = 0; i < len1 + 1; ++i){
for(int j = 0; j < len2 + 1; ++j){
if(0 == i) dp[i][j] = j;
else if(0 == j) dp[i][j] = i;
else{
if(s1[i] != s2[j])
dp[i][j] = min(min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1), dp[i][j - 1] + 1);
else
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j] + 1), dp[i][j - 1] + 1);
}
}
}
return dp[len1][len2];
}
};
int main(){
Solution sol;
string s1, s2;
while(getline(cin, s1) && getline(cin, s2))
cout << sol.minDistance(s1, s2) << endl;
return 0;
} 
#include<stdio.h>
#define len 500
int getmin(int a, int b, int c) {
if(a <= b && a <= c) {
return a;
} else if (b <= a && b <= c) {
return b;
} else if (c <= a && c <= b) {
return c;
} else {
return -1;
}
}
int getLev(char a[len], char b[len]) {
int m = strlen(a);
int n = strlen(b);
int cost = 0, lev[len][len] = {0};
for(int i = 0; i <= m; i++) {
lev[i][0] = i;
}
for(int j = 0; j <= n; j++) {
lev[0][j] = j;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(a[i-1] == b[j-1]) {
lev[i][j] = lev[i-1][j-1];
} else {
lev[i][j] = getmin(lev[i][j-1] + 1, lev[i-1][j] + 1, lev[i-1][j-1] + 1);
}
}
}
return lev[m][n];
}
int main() {
char a[len] = {0};
char b[len] = {0};
while(gets(a) && gets(b)) {
printf("%d\n", getLev(a,b));
}
}
/*
如何计算编辑距离:
1.两字字串都为空，编辑距离为0
2.当其中一个为空时，编辑距离为另外一个字串的长度。
3.当两个字串非空时（长度分别为i 和 j时），取下面3种情况最小值：
3.1 当i-1 和 j的编辑距离已知时，直接+1 为 i和j的编辑距离
3.2 当i 和 j-1的编辑距离已知时，直接+1 为 i和j的编辑距离
3.3 当i-1 和 j-1的编辑距离已知时，如果i字符和j字符相等则+0，如果不相等则+1为 i和j的编辑距离。
应该用动态规划：
int dp[m+1][n+1] //定义长度为i的字串和长度为j的字串之间的编辑距离
两个字符串最前面插入一个空字符，初始化[i][0] base case 为i，初始化[0][j] base case 为j；
编写状态转移方程。
*/
int cal_distance(string sline1,string sline2)
{
if ((sline1.empty())&&(sline2.empty())){
return 0;
}
if ((sline1.empty())&&(!sline2.empty())){
return sline2.size();
}
if ((!sline1.empty())&&(sline2.empty())){
return sline1.size();
}
sline1.insert(sline1.begin(),' ');
sline2.insert(sline2.begin(),' ');
int m = sline1.size();
int n = sline2.size();
vector<vector<int>> dp(m, vector<int>(n,0));//定义长度为i的字串和长度为j的字串之间的编辑距离
for (int i=0;i<m;i++){
dp[i][0] = i;
}
for (int j=0;j<n;j++){
dp[0][j] = j;
}
for (int i=1;i<m;i++){
for (int j=1;j<n;j++){
int add;
if (sline1[i] == sline2[j]){
add = 0;
}
else{
add = 1;
}
int dp1 = dp[i-1][j-1] + add;
int dp2 = dp[i-1][j]+1;
int dp3 = dp[i][j-1]+1;
if (dp1>dp2){
dp1 = dp2;
}
if (dp1>dp3){
dp1 = dp3;
}
dp[i][j] = dp1;
}
}
return dp[m-1][n-1];
}
int _tmain(int argc, _TCHAR* argv[])
{
string sline1, sline2;
while(cin >> sline1)
{
cin >> sline2;
int length = cal_distance(sline1,sline2);
cout << length <<endl;
}
return 0;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String a = in.nextLine();
String b = in.nextLine();
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
//初始化状态
for(int i = 1;i <= m;i++){
dp[i][0] = i;
}
for(int j = 1;j <= n;j++){
dp[0][j] = j;
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(a.charAt(i - 1) == b.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
}
}
}
System.out.println(dp[m][n]);
}
} 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
String s1 = " " + cin.next(), s2 = " " + cin.next();
System.out.println(calStringDistance(s1, s2));
}
}
public static int calStringDistance(String charA, String charB) {
int n = charA.length(), m = charB.length();
int[][] lev = new int[n][m];
int cost;
for (int i = 0; i < n; i++) lev[i][0] = i;
for (int j = 0; j < m; j++) lev[0][j] = j;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
char ch1 = charA.charAt(i), ch2 = charB.charAt(j);
if (ch1 == ch2) cost = 0;
else cost = 1;
lev[i][j] = getMin(lev[i - 1][j] + 1, lev[i][j - 1] + 1, lev[i - 1][j - 1] + cost);
}
}
return lev[n - 1][m - 1];
}
public static int getMin(int a, int b, int c) {
a = Math.min(a, b);
b = Math.min(b, c);
return Math.min(a, b);
}
}
最小编辑距离，经典的动态规划问题之一，类似的还有最大公共子串，最大公共序列，最大递增序列，01
背包问题等等
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
string s1,s2;
while(cin>>s1>>s2){
int len1=s1.size();
int len2=s2.size();
vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
for(int i=1;i<=len1;i++){
dp[i][0]=i;
}
for(int j=1;j<=len2;j++){
dp[0][j]=j;
}
dp[0][0]=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1];
else{
int tem=min(dp[i-1][j],dp[i][j-1]);
dp[i][j]=min(dp[i-1][j-1],tem)+1;
}
}
}
cout<<dp[len1][len2]<<endl;
}
return 0;
} 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String strA = in.next();
String strB = in.next();
int cost = strEditCost(strA, strB);
System.out.println(cost);
}
in.close();
}
public static int strEditCost(String strA, String strB){
int m = strA.length() + 1;
int n = strB.length() + 1;
int[][] dp = new int[m][n];
// 初始化0列0行先,这个距离是可以预先知道的
for(int i = 0;i<m;i++) {
dp[i][0] = i;
}
for(int j = 0;j<n;j++) {
dp[0][j] = j;
}
// 当 i,j都是大于0时
for(int i = 1;i<m;i++) {
for(int j=1;j<n;j++) {
int cout1 = Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1);
int dc = 1;
if(strA.charAt(i-1) == strB.charAt(j-1)) {
dc = 0;
}
int cout2 = Math.min(cout1,dp[i-1][j-1]+dc);
dp[i][j] = cout2;
}
}
return dp[m-1][n-1];
}
} 
#include<iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
string a,b;
while(cin>>a>>b)
{
int n = a.size(),m = b.size();
vector<vector<int>>dp(n+1,vector<int>(m+1));/*dp[x][y]代表将a字符串的前x个字符（从1编号，a的前1个字符为a[0],
前两个字符为a[0]和a[1]）转换成b字符串的前y个字符*/
for (int i=0; i<=n; i++) dp[i][0] = i;
for (int j=0; j<=m; j++) dp[0][j] = j;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; ++j)
{
int d1 = dp[i-1][j] +1,d2 = dp[i][j-1]+1,d3 = dp[i-1][j-1];
if(a[i-1]!=b[j-1]) d3+=1; //注意由于a的前i-1个字符时从1编号，则第i个字符也是从1编号，为a[i-1]，同理b[j-1]
dp[i][j] = min(min(d1,d2),d3);
}
cout<<dp[n][m]<<endl;
}
return 0;
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
String s1=input.nextLine();
String s2=input.nextLine();
System.out.println(stringDistance(s1.toCharArray(), s2.toCharArray()));
}
}
public static int stringDistance(char[] a, char[] b){
int[][] len = new int[a.length + 1][b.length + 1];
for (int i = 0; i < len.length; i++) {
len[i][0] = i;
}
for (int j = 0; j < len[0].length; j++) {
len[0][j] = j;
}
for (int i = 1; i < len.length; i++) {
for (int j = 1; j < len[0].length; j++) {
if (a[i - 1] == b[j - 1]) {
len[i][j] = len[i - 1][j - 1];
} else {
len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
}
}
}
return len[len.length - 1][len[0].length - 1];
}
}
import java.util.Scanner;
public class P052StringDistance {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String strA = sc.next();
String strB = sc.next();
System.out.println(calStrDis(strA, strB, strA.length(), strB.length()));
}
sc.close();
}
public static int calStrDis(String strA, String strB, int m, int n) {
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if(i == 0)//strA为空。
dp[i][j] = j;
else if(j == 0)//strB为空。
dp[i][j] = i;
else if(strA.charAt(i - 1) == strB.charAt(j - 1))//strA和strB最后一个字符相同。
dp[i][j] = dp[i-1][j-1];
else//strA和strB最后一个字符不同。
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);//strA的所有操作：插入，删除，替换。 }
}
return dp[m][n];
/*//直接递归，运行超时。
if(m == 0) return n;
if(n == 0) return m;
if(strA.charAt(m - 1) == strB.charAt(n - 1))
return calStrDis(strA, strB, m - 1, n - 1);
return 1 + min(calStrDis(strA, strB, m, n - 1), calStrDis(strA, strB, m - 1, n), calStrDis(strA, strB, m - 1, n - 1));
*/
}
public static int min(int x, int y, int z) {
if(x < y && x < z)
return x;
else if(y < x && y < z){
return y;
else
return z;
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
String str1 = scan.nextLine();
String str2 = scan.nextLine();
System.out.println(calStringDistance(str1, str2));
}
scan.close();
}
private static int calStringDistance(String str1, String str2){
int len1 = str1.length();
int len2 = str2.length();
int[][] distance = new int[len1+1][len2+1];
for(int i=1; i<=len1; i++){
distance[i][0]=i;
}
for(int j=1; j<=len2; j++){
distance[0][j]=j;
}
int a=0, b=0, c=0;
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
a = distance[i][j-1]+1;
b = distance[i-1][j]+1;
c = str1.charAt(i-1)==str2.charAt(j-1)? distance[i-1][j-1]:distance[i-1][j-1]+1;
distance[i][j]= Math.min(Math.min(a,b), c);
}
}
return distance[len1][len2];
}
}
//思路主要：
A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。
1．删除A串的第一个字符，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
2．删除B串的第一个字符，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
3．修改A串的第一个字符为B串的第一个字符，然后计算A[2,…,lenA]和
B[2,…,lenB]的距离。
4．修改B串的第一个字符为A串的第一个字符，然后计算A[2,…,lenA]和
B[2,…,lenB]的距离。
5．增加B串的第一个字符到A串的第一个字符之前，然后计算
A[1,…,lenA]和B[2,…,lenB]的距离。
6．增加A串的第一个字符到B串的第一个字符之前，然后计算
* 设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
* 设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
*
* 设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
* 当ai==bj时 显然 L(i,j) = L(i-1,j-1)
* 当ai!=bj时
*
* 若将它们修改为相等，则对两个字符串至少还要操作L(i-1,j-1)次
* 若删除ai或在bj后添加ai，则对两个字符串至少还要操作L(i-1,j)次
* 若删除bj或在ai后添加bj，则对两个字符串至少还要操作L(i,j-1)次
* 此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
*
* 显然，L(i,0)=i，L(0,j)=j, 再利用上述的递推公式，可以直接计算出L(i,j)值。
package com.wenjie.huawei;
import java.util.Scanner;
public class CalStringDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
System.out.println(stringDistance(str1.toCharArray(),str2.toCharArray()));
}
}
private static int stringDistance(char[] a, char[] b) {
int[][] len = new int[a.length + 1][b.length + 1];
for (int i = 0; i < len.length; i++) {
len[i][0] = i;
}
for (int j = 0; j < len[0].length; j++) {
len[0][j] = j;
}
for (int i = 1; i < len.length; i++) {
for (int j = 1; j < len[0].length; j++) {
if (a[i - 1] == b[j - 1]) {
len[i][j] = len[i - 1][j - 1];
} else {
len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
}
}
}
return len[len.length - 1][len[0].length - 1];
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String strA = in.next();
String strB = in.next();
int ic = 1;
int dc = 1;
int rc = 1;
int cost = strEditCost(strA, strB, ic, dc, rc);
System.out.println(cost);
}
in.close();
}
public static int strEditCost(String strA, String strB, int ic, int dc, int rc){
/* 字符串之间的距离，编辑距离，将strA编辑成strB所需的最小代价
* 编辑操作包括插入一个字符、删除一个字符、替换一个字符
* 分别对应的代价是ic、dc、rc，insert cost、delete cost、replace cost
* strA[x-1]代表strA的第x个字符，注意下标是从0开始的,strA[y-1]代表strA的第y个字符
* 定义一个代价矩阵为(N+1)*(M+1)，M N 表示strA strB的长度
* dp[x][y]表示strA的前x个字符串编辑成 strB的前y个字符所花费的代价
* dp[x][y]是下面几种值的最小值：
* 1、dp[x][y] = dp[x-1][y] + dc
* dp[x-1][y]将strA的前x-1个字符编辑成strB的前y个字符的代价已知，
* 那么将将strA的前x个字符编辑成strB的前y个字符的代价dp[x][y]就是dp[x-1][y] + dc
* 相当于strA的前x-1个字符编辑成strB的前y个字符，现在变成了strA的前x个字符，增加了一个字符，要加上删除代价
* 2、dp[x][y] = dp[x][y-1] + ic
* dp[x][y-1]将strA的前x个字符编辑成strB的前y-1个字符的代价已知，
* 现在变为strB的前y个字符，相应的在strA前x个操作代价的基础上插入一个字符
* 3、dp[x][y] = dp[x-1][y-1]
* dp[x-1][y-1]将strA的前x-1个字符编辑成strB的前y-1个字符的代价已知，
* strA的第x个字符和strB的第y个字符相同，strA[x-1] == strB[y-1]，没有引入操作
* 4、dp[x][y] = dp[x-1][y-1] + rc
* strA的第x个字符和strB的第y个字符不相同，strA[x-1] ！= strB[y-1]，
* 在strA的前x-1个字符编辑成strB的前y-1个字符的代价已知的情况下，
* 计算在strA的前x字符编辑成strB的前y个字符的代价需要加上替换一个字符的代价
* */
int m = strA.length();
int n = strB.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= n; i++) dp[0][i] = i*ic;
for (int i = 1; i <= m; i++) dp[i][0] = i*dc;
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
int cost1 = dp[x-1][y] + dc;
int cost2 = dp[x][y-1] + ic;
int cost3 = 0;
if(strA.charAt(x-1) == strB.charAt(y-1))
cost3 = dp[x-1][y-1];
else
cost3 = dp[x-1][y-1] + rc;
dp[x][y] = Math.min(cost1, cost2);
dp[x][y] = Math.min(dp[x][y], cost3);
}
}
return dp[m][n];
}
}
def editDistance(str1, str2):
len1, len2 = len(str1) + 1, len(str2) + 1
dp = [[0 for i in range(len2)] for j in range(len1)]
for i in range(len1):
dp[i][0] = i
for j in range(len2):
dp[0][j] = j
for i in range(1, len1):
for j in range(1, len2):
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
return dp[-1][-1]
while True:
try:
print(editDistance(input(), input()))
except:
break
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
