首页 > 试题广场 >

计算字符串的编辑距离

[编程题]计算字符串的编辑距离
  • 热度指数:131018 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的,故又叫 Levenshtein Distance 。

例如:

字符串A: abcdefg

字符串B: abcdef

通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求:

给定任意两个字符串,写出一个算法计算它们的编辑距离。

数据范围:给定的字符串长度满足




输入描述:

每组用例一共2行,为输入的两个字符串



输出描述:

每组用例输出一行,代表字符串的距离

示例1

输入

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行了,只保留了最后一行
//这种方法空间复杂度就比较低
    }
}
发表于 2022-03-21 23:14:15 回复(0)
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;
    }
    
}

发表于 2021-12-08 15:45:02 回复(0)
while True:
    try:
        s1, s2 = input(), input()
        s1 = list(s1)
        s2 = list(s2)
        s1.insert(0, "")
        s2.insert(0, "")
        lens1 = len(s1)
        lens2 = len(s2)
        dp = []
        for y in range(lens2):
            s = []
            for x in range(lens1):
                if y == 0:
                    s.append(x)
                else:
                    s.append(0 * x)
            dp.append(s)
        # 初始化边界值
        for y in range(lens2):
            dp[y][0] = y
#         print(dp)

        dp[0][0] = 0
        for y in range(1, lens2):
            ss2 = s2[y]
            for x in range(1, lens1):
                ss1 = s1[x]
                if ss1 == ss2:
                    dp[y][x] = dp[y - 1][x - 1]
                else:
                    dp[y][x] = min(dp[y - 1][x - 1], dp[y - 1][x], dp[y][x - 1]) + 1
        print(dp[-1][-1])
    except:
        break
发表于 2021-11-13 22:57:44 回复(0)
动态规划解题
有两个字符串s1[0...m-1]和s2[0...n-1]。s1转换为s2的最后一步有三种情况:
1、假设s1[0...m-2] 已转为为s2[0...n-1],最小距离为a。那么最后一步就是,s1[0...m-1] 删除末尾一个字符,就得到s2[0...n-1];等价于,s2[0...n-1]末尾插入一个字符得到s1[0...m-1] 。
2、假设s1[0...m-1] 已转为为s2[0...n-2],最小距离为b。那么最后一步就是,s1[0...m-1] 末尾插入一个字符,就得到s2[0...n-1];等价于,s2[0...n-2]删除末尾一个字符得到s1[0...m-1] 。
3、假设s1[0...m-2] 已转为为s2[0...n-2],最小距离为c那么最后一步就是,s1[0...m-1] 末尾替换一个字符,得到s2[0...n-1];等价于,s2[0...n-1]末尾替换一个字符得到s1[0...m-1] 。
那么,s1[0...m-1]转换为s2[0...n-1] 的最小距离为:min(a+1, b+1, c)或min(a+1, b+1, c+1)。
若s1[m - 1] == s2[n - 1] 那么就是min(a+1, b+1, c);
若s1[m - 1] != s2[n - 1] 那么就是min(a+1, b+1, c+1).
以上这三种情况,又可以各自在分三种情况;以此类推,问题可以不断划分为一个个子问题。
#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;
}

发表于 2021-10-22 21:19:06 回复(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));
    }
}
发表于 2021-08-17 23:18:46 回复(0)
/*
如何计算编辑距离:
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;
}

发表于 2021-04-18 16:27:17 回复(0)
动态规划,dp[i][j]代表i到j的编辑距离
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]);
        }
    }


发表于 2021-04-15 15:37:45 回复(0)
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);
    }
}

发表于 2020-08-22 20:30:14 回复(0)
最小编辑距离,经典的动态规划问题之一,类似的还有最大公共子串,最大公共序列,最大递增序列,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;
}

发表于 2020-02-16 20:08:55 回复(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];
    }
}


发表于 2019-11-02 23:47:13 回复(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;
}

发表于 2018-07-08 01:01:58 回复(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];
    }
}

发表于 2018-06-29 15:56:37 回复(0)
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;
    }
                    

发表于 2018-06-12 22:55:51 回复(0)
import java.util.Scanner;

public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()){
String s1=in.nextLine();
String s2=in.nextLine();
System.out.println(calStringDistance(s1,s2));
}
}

private static int calStringDistance(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
if(len1==0){
return len2;
}
if(len2 ==0){
return len1;
}
int[][] a = new int[len1+1][len2+1];
for(int i=0;i<len1+1;i++){
a[i][0]=i;
}
for(int j=0;j<len2+1;j++){
a[0][j] =j;
}
for(int i=1;i<len1+1;i++){
for(int j=1;j<len2+1;j++){
int temp=Math.min(a[i-1][j]+1, a[i][j-1]+1);
int num=c1[i-1]==c2[j-1]?0:1;
a[i][j]=Math.min(temp, a[i-1][j-1]+num);
}
}
return a[len1][len2];
}
}
编辑于 2017-04-17 16:50:34 回复(0)
import java.util.*;
/**
*
* @author zhangxf0406
* 动态规划--计算字符串的距离
*/
public class Main {
public static void calStringDistance(char[] source , char[] target){
    int [][]dp = new int[source.length + 1][target.length + 1];
    for(int i = 0 ; i < source.length + 1 ; i++)
        dp[i][0] = i;
    for(int j = 0 ; j < target.length + 1 ; j++)
        dp[0][j] = j;
    for(int i = 1 ; i < source.length + 1 ; i++){
        for(int j = 1 ; j < target.length + 1 ; j++){
            if(source[i-1] == target[j-1])
                dp[i][j] = dp[i-1][j-1];
        else{
            dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1 , dp[i][j-1] + 1) , dp[i-1][j-1] + 1);
            }
        }
    }
    System.out.println(dp[source.length][target.length]);
}
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String a = scanner.next();
            String b = scanner.next();
            char [] source = a.toCharArray();
            char [] target = b.toCharArray();
            calStringDistance(source, target);
        }
    scanner.close();
    }
}

编辑于 2017-03-09 10:59:59 回复(1)
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];
    }
}

发表于 2016-08-24 19:31:10 回复(2)

import java.util.Scanner;

public class Main{
public static int min(int a,int b,int c){//输出三个数的最小值
int min=a>b?b:a;
return min<c?min:c;
}
public static int dp(String a,String b){
int m=a.length();
int n=b.length();
int[][] arr=new int[m+1][n+1];
for (int i = 1; i <=m; i++) {
            arr[i][0]=i;
for (int j = 1; j <=n; j++) {
                arr[0][j]=j;
if (a.charAt(i-1)==b.charAt(j-1)) {
arr[i][j]=arr[i-1][j-1];
}
else {
arr[i][j]=min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1])+1;
}
}
}
return arr[m][n];
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
String a=scanner.next();
String b=scanner.next();
System.out.println(dp(a, b));
}
}
}
发表于 2016-08-17 12:02:32 回复(0)
//思路主要:

u 如果两个串的第一个字符相同 ,如A=xabcdae和B=xfdfa,只要计算

A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。

u 如果两个串的第一个字符不相同 ,那么可以进行如下的操作:

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串的第一个字符之前,然后计算

A[2,…,lenA]和B[1,…,lenB]的距离。
动态规划思路为:
 * 设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];
    }
}


编辑于 2017-06-14 21:27:16 回复(6)
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];
	}
}


编辑于 2017-06-28 12:54:18 回复(5)

python solution:

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
发表于 2017-10-17 14:57:35 回复(11)