首页 > 试题广场 >

计算字符串的编辑距离

[编程题]计算字符串的编辑距离

热度指数：153642 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，在任意位置插入一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，删除任意一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，替换任意一个字符。

$\hspace{15pt}$ 现在，对于给定的字符串 $s$ 和 $t$ ，请计算出它们的编辑距离。

输入描述:

第一行输入一个长度为 ，仅由小写字母组成的字符串 。
第二行输入一个长度为 ，仅由小写字母组成的字符串 。

输出描述:

输出一个整数，表示  和  的编辑距离。

示例1

输入

abcdefg
abcdef

输出

说明

在这个样例中，可以选择将  末尾的  删除。当然，也可以选择在  末尾插入 。

算法知识视频讲解

Java

//201910101754657

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int[][] res = new int[str1.length()][str2.length()];
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                char c1 = str1.charAt(i);
                char c2 = str2.charAt(j);
                if (i == 0) {
                    res[i][j] = str2.substring(0, j + 1).indexOf(c1) >= 0 ? j : j + 1;
                    continue;
                }
                if (j == 0) {
                    res[i][j] = str1.substring(0, i + 1).indexOf(c2) >= 0 ? i : i + 1;
                    continue;
                }
                if (c1 == c2) {
                    res[i][j] = res[i - 1][j - 1];
                } else {
                    int r1 = res[i][j - 1] + 1;
                    int r2 = res[i - 1][j] + 1;
                    int r3 = res[i - 1][j - 1] + 1;
                    res[i][j] = Math.min(r1, Math.min(r2, r3));
                }
            }
        }
        System.out.println(res[str1.length() - 1][str2.length() - 1]);
    }
}

编辑于 2024-03-19 01:03:53 回复(0)

Java

想要个oooffer

package hj;

import javax.naming.Name;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @className: _5_2
 * @author: Lian
 * @date: 2023-10-04 11:06
 */
public class _5_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int a=str1.length,b=str2.length;
        int[][] arr=new int[a+1][b+1];
        for(int i=0;i<a+1;i++){
            for(int j=0;j<b+1;j++){
                arr[i][j]=Integer.MAX_VALUE;
            }
        }
        for(int i=0;i<=a;i++){
            arr[i][0]=i;
        }
        for(int i=0;i<=b;i++){
            arr[0][i]=i;
        }

        for(int i=1;i<=a;i++){
            for(int j=1;j<=b;j++){
                if(str1[i-1]==str2[j-1]){
                    arr[i][j]=arr[i-1][j-1];
                }
                arr[i][j]=Math.min(arr[i][j],arr[i-1][j]+1);
                arr[i][j]=Math.min(arr[i][j],arr[i][j-1]+1);
                arr[i][j]=Math.min(arr[i][j],arr[i-1][j-1]+1);
            }
        }

        System.out.println(arr[a][b]);
    }
}

发表于 2023-10-04 16:52:26 回复(0)

Java

锰锰在睡觉

import java.lang.Math;

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String a = in.nextLine();

String b = in.nextLine();

int[][] c = new int[a.length() + 1][b.length() + 1];

for (int i = 0; i < a.length() + 1; i++) {

c[i][0] = i;

}

for (int i = 0; i < b.length() + 1; i++) {

c[0][i] = i;

}

for (int i = 1; i < a.length() + 1; i++) {

for (int j = 1; j < b.length() + 1; j++) {

if (a.charAt(i - 1) == b.charAt(j - 1)) {

c[i][j] = c[i - 1][j - 1];

} else {

c[i][j] = Math.min(c[i - 1][j - 1], Math.min(c[i - 1][j], c[i][j - 1])) + 1;

}

System.out.print(c[a.length()][b.length()]);

}

发表于 2023-09-21 23:26:33 回复(0)

Java

GCID

将字符串输入char数组A,B

则动态规划方程：DP[i][j]=min{DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+(A[i-1]==B[j-1]?0:1)}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] A=in.nextLine().toCharArray();
        char[] B=in.nextLine().toCharArray();
        int[][] DP=new int[A.length+1][B.length+1];
        DP[0][0]=0;
        for(int i=0;i<=A.length;i++){
            for(int j=0;j<=B.length;j++){
                if(i!=0&&j!=0){
                    DP[i][j]=i+j;
                    DP[i][j]=Math.min(DP[i][j],DP[i-1][j]+1);
                    DP[i][j]=Math.min(DP[i][j],DP[i][j-1]+1);
                    DP[i][j]=Math.min(DP[i][j],DP[i-1][j-1]+(A[i-1]==B[j-1]?0:1));
                }else if(i!=0){
                    DP[i][j]=i;
                }else if(j!=0){
                    DP[i][j]=j;
                }
            }
        }
        System.out.println(DP[A.length][B.length]);
    }
}

发表于 2023-09-07 22:29:45 回复(0)

Java

犯花乖乖

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String strA = in.nextLine();
        String strB = in.nextLine();
         System.out.print(getEditDistance(strA,strB));
    }
    public static int getEditDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        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++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

发表于 2023-05-18 09:58:07 回复(0)

Java

打不死的小伍六七

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int total = 0;

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNext()) { // 注意 while 处理多个 case

String str1 = in.next();

String str2 = in.next();

int[] aa = new int[128];

int[] bb = new int[128];

for (int i = 0; i < str1.length(); i++) {

int num1 = (int)str1.charAt(i);

aa[num1]+=1;

}

for (int i = 0; i < str2.length(); i++) {

int num2 = (int)str2.charAt(i);

bb[num2]+=1;

}

for (int i = 0; i < 128; i++) {

if (!(aa[i] == 0 && bb[i] == 0)) {

total += Math.abs(aa[i] - bb[i]);

}

System.out.println(total);

}

发表于 2023-03-29 21:10:05 回复(1)

Java

自由的风。

用一个二维数组来记录距离，第一维表示的是第一个字符串的长度，第二维表示的是第二个字符串的长度。当某一个字符串长度为0时，距离就是另一个字符串的长度。遍历这个二维数组。当两个字符串的最后一个字符长度不同时，有三种解决方案：删除前一个字符串的最后一个字符，删除后一个字符串的最后一个字符，将其中一个字符串的最后一个字符替换，分别对应二维数组左上方三个坐标，取其中最小值加上本次操作1就是当前最小距离。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String stra=br.readLine();
        String strb=br.readLine();
        int num1=0;
        int[][] dis=new int[stra.length()+1][strb.length()+1];
        for(int i=0;i<=stra.length();i++){
            dis[i][0]=i;
        }
        for(int i=0;i<=strb.length();i++){
            dis[0][i]=i;
        }
        for(int i=1;i<=stra.length();i++){
            for(int j=1;j<=strb.length();j++){
                if(stra.charAt(i-1)==strb.charAt(j-1)){
                    dis[i][j]=dis[i-1][j-1];
                }else{
                    num1=Math.min(dis[i-1][j],dis[i][j-1]);
                    dis[i][j]=Math.min(num1,dis[i-1][j-1])+1;
                }
            }
        }
        System.out.println(dis[stra.length()][strb.length()]);
        
    }
    
}

发表于 2022-09-03 12:53:41 回复(1)

Java

牛客192353924号

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();

int n1 = str1.length();
int n2 = str2.length();

char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
//dp[i,j]表示s1前i个子字符串和s2前j个子字符串的最短编辑距离是多少。
int[][] dp = new int[n1 + 1][n2 + 1];
for(int i = 1;i <= n1;i++){
dp[i][0] = dp[i - 1][0] + 1;
}
for(int i = 1;i <= n2;i++){
dp[0][i] = dp[0][i - 1] + 1;
}
for(int i = 1;i <= n1;i++){
for(int j = 1;j <= n2;j++){
if(c1[i - 1] == c2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.min(dp[i][j],Math.min(dp[i - 1][j],dp[i][j - 1]) + 1);

}
}
}
System.out.println(dp[n1][n2]);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();

int n1 = str1.length();
int n2 = str2.length();

char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
//dp[i,j]表示s1前i个子字符串和s2前j个子字符串的最短编辑距离是多少。
int[][] dp = new int[n1 + 1][n2 + 1];
for(int i = 1;i <= n1;i++){
dp[i][0] = dp[i - 1][0] + 1;
}
for(int i = 1;i <= n2;i++){
dp[0][i] = dp[0][i - 1] + 1;
}
for(int i = 1;i <= n1;i++){
for(int j = 1;j <= n2;j++){
if(c1[i - 1] == c2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.min(dp[i][j],Math.min(dp[i - 1][j],dp[i][j - 1]) + 1);

}
}
}
System.out.println(dp[n1][n2]);
}
}

发表于 2022-08-11 16:30:16 回复(0)

Java

牛客209952369号

动态规划

import java.util.*;

public class Main {
    //动态规划
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        int len1 = s1.length(),len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化
        for(int i = 1;i <= len2;i++) dp[0][i] = i;
        for(int i = 1;i <= len1;i++) dp[i][0] = i;
        for(int i = 1;i <= len1;i++){
            for(int j = 1;j<= len2;j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    //替换
                    dp[i][j] = dp[i][j] == 0 ? dp[i - 1][j - 1] + 1 : Math.min(dp[i - 1][j - 1] + 1,dp[i][j]);
                    //插入
                    dp[i][j] = Math.min(dp[i][j - 1] + 1,dp[i][j]);
                    //删除
                    dp[i][j] = Math.min(dp[i - 1][j] + 1,dp[i][j]);
                }
            }
        }
        System.out.println(dp[len1][len2]);
    }
}

发表于 2022-08-02 15:37:45 回复(0)

Java

0offer选手申请出战

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.nextLine().toCharArray();
        char[] b = sc.nextLine().toCharArray();
        int n = a.length, m = b.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1));
            }
        }
        System.out.println(dp[n][m]);
    }
}

发表于 2022-08-01 11:58:09 回复(0)

Java

这是我的响亮的名字

通过暴力递归改出来的动态规划

public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        
        int N = str1.length();
        int M = str2.length();
        
        int [][] dp = new int[N][M];
        
        //1
        dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 0 : 1;
        
        //2
        for(int j = 1; j < M; j++){
            dp[0][j] = str1.charAt(0) == str2.charAt(j) ? j : dp[0][j-1]+1;
        }
        
        //3
        for(int i = 1; i < N; i++){
            dp[i][0] = str1.charAt(i) == str2.charAt(0) ? i : dp[i-1][0]+1;
        }
        
        //4
        for(int i = 1; i < N; i++){
            for(int j = 1; j < M; j++){
                int p1 = dp[i-1][j]+1;
                int p2 = dp[i][j-1]+1;
                int p3 = str1.charAt(i) == str2.charAt(j) ? dp[i-1][j-1] : dp[i-1][j-1]+1;
                int min = Math.min(p1, p2);
                min = Math.min(min, p3);
                dp[i][j] = min;
            }
        }
        
        System.out.println(dp[N-1][M-1]);
    }
    
    //暴力递归复杂度高，测试用例一个都过不了
    public static int process(String str1, String str2, int i, int j){
        //1
        if(i == 0 && j == 0) {
            return str1.charAt(0) == str2.charAt(0) ? 0 : 1;
            
            //2
        } else if(i == 0){
            if(str1.charAt(0) == str2.charAt(j)){
                return j;
            } else {
                return process(str1, str2, 0, j-1)+1;
            }
            
            //3
        } else if(j == 0){
            if(str1.charAt(i) == str2.charAt(0)){
                return i;
            } else {
                return process(str1, str2, i-1, 0)+1;
            }
            
            //4
        } else{
            int p1 = process( str1,  str2,  i-1,  j)+1;
            int p2 = process( str1,  str2,  i,  j-1)+1;
            int p3 = str1.charAt(i) == str2.charAt(j) ? process( str1,  str2,  i-1,  j-1) : process( str1,  str2,  i-1,  j-1)+1;
            int min = Math.min(p1, p2);
            min = Math.min(min, p3);
            return min;
        }
    }

发表于 2022-07-23 22:15:14 回复(0)

Java

bug郭

图片说明

import java.util.*;
public class Main{
    public static int distancefun(String str1,String str2){
        int row = str1.length();
        int col = str2.length();
        int[][] dp = new int[row+1][col+1];
        //初始状态:f(i,0) = i; f(0,j) = j;
        //状态转移: f(i,j) = str[i]==str2[j]? f(i-1,j-1): min(f(i-1,j),f(i,j-1),f(i-1,j-1))+1
        //状态定义: f(i,j)  str1 前 i 个子串和 str2 前j 个子串的最小编辑距离
        //返回结果:f(row,col);
        for(int i = 0;i<= row;i++){
            dp[i][0] = i;
        }
        for(int i = 0;i<=col;i++){
            dp[0][i] = i;
        }
        for(int i = 1;i<=row;i++){
            for(int j = 1;j<=col;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int min = Math.min(dp[i-1][j],dp[i][j-1]);
                     dp[i][j] = Math.min(dp[i-1][j-1],min) + 1;
                }
            }
        }
        return dp[row][col];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
         int result = distancefun(str1,str2);
        System.out.println(result);
    }
}

发表于 2022-05-05 22:20:20 回复(0)

Java

M870RushB

哈哈动态规划寄咯

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s1 = sc.next();
            String s2 = sc.next();
            int dp[][] = new int[s1.length()+1][s2.length()+1];
            dp[0][0] = 0;
            for(int i = 1;i<dp.length;i++){
                dp[i][0] = i;
            }
            for(int i = 1;i<dp[0].length;i++){
                dp[0][i] = i;
            }
            for(int i = 1;i<dp.length;i++){
                for(int j = 1;j<dp[0].length;j++){
                    if(s1.charAt(i-1)==s2.charAt(j-1))
                    {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    else {
                        dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
                    }
                }
            }
            System.out.println(dp[s1.length()][s2.length()]);
        }
    }
}

发表于 2022-04-28 16:08:19 回复(0)

Java

来学习的小张

import java.util.*;
public class Main{
    public static int fun(String s1,String s2){
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        int len1 = ch1.length;
        int len2 = ch2.length;
        int[][] res = new int[len1 + 1][len2 + 1];
        //初始化第一行和第一列
        for(int i = 0;i <= len1;i++){
            res[i][0] = i;
        }
        for(int j = 0;j <= len2;j++){
            res[0][j] = j;
        }
        
         for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                //求插入和删除的最小值
                res[i][j] = Math.min(res[i - 1][j],res[i][j - 1])+1;
                //和替换进行比较
                if(ch1[i - 1] == ch2[j - 1]){
                     res[i][j] = Math.min(res[i][j],res[i - 1][j - 1]);
                }else{
                     res[i][j] = Math.min(res[i][j],res[i - 1][j - 1] + 1);
                }
            }
        }
        return res[len1][len2];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
             String s1 = sc.nextLine();
             String s2 = sc.nextLine();
            System.out.println( fun(s1,s2));
        }
    }
}

发表于 2022-04-25 11:29:44 回复(0)

Java

一剑飘红2021

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)

Java

牛客834967964号

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            dp[0][0] = 0;
            for (int i = 0; i <= str1.length(); i++){
                for (int j = 0; j <= str2.length(); j++){
                    if (i == 0) dp[i][j] = j;
                    else if (j == 0) dp[i][j] = i;
                    else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                            dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), 
                                             dp[i - 1][j - 1]) + 1; 
                }
            }
            System.out.println(dp[str1.length()][str2.length()]);
        }
    }
}

应该是经典竞赛题，没做过很难做出来；B站有讲解：

https://www.bilibili.com/video/BV1r64y1Q7pJ?from=search&seid=15710822689247570421&spm_id_from=333.337.0.0

发表于 2021-12-07 21:49:08 回复(0)

Java

奥因克

import java.util.*;
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(distance(str1,str2));
        }
    }
    public static int distance(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i = 0; i < len1+1;i++){
            dp[i][0] = i;
        }
        for(int i = 0; i < len2+1;i++){
            dp[0][i] = i;
        }
        for(int i = 1; i < len1+1;i++){
            for(int j = 1; j < len2+1;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[len1][len2];
    }
}

发表于 2021-12-05 01:27:51 回复(0)

Java

LSur

import java.util.Scanner;

/**
 * @author Yuliang.Lee
 * @version 1.0
 * @date 2021/9/23 18:00
 * 计算字符串的距离：
    Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。
    许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
    编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
    Ex：
    字符串A: abcdefg
    字符串B: abcdef
    通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
    要求：给定任意两个字符串，写出一个算法计算它们的编辑距离。

 * 解题思路：
    这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。
    迭代公式：
        lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；
        插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；
        如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0;
        如果a[i] != b[j]，则需要考虑3种情况的可能：
            a中插入字符，即lev[i][j] = lev[i-1][j] + 1;
            b中插入字符，即lev[i][j] = lev[i][j-1] + 1;
            a[i]替换成b[j]，lev[i][j] = lev[i-1][j-1] + 1;
        取这3种情况的最小值。
    细节补充：
        二维数组的初始化以及迭代算法的修正体现在代码实现中。

 * 示例：
    输入：
        abcdefg
        abcdef
        abcde
        abcdf
        abcde
        bcdef
    输出：
        1
        1
        2
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            int len1 = str1.length();
            int len2 = str2.length();
            int[][] lev = new int[len1][len2];
            // 初始化
            if (str1.charAt(0) == str2.charAt(0)) {
                lev[0][0] = 0;
            } else {
                lev[0][0] = 1;
            }
            // dp填充数组
            for (int i = 0; i < len1; i++) {
                char a = str1.charAt(i);
                for (int j = 0; j < len2; j++) {
                    char b = str2.charAt(j);
                    if (a == b) {
                        if (i > 0 && j > 0) {
                            lev[i][j] = lev[i-1][j-1];
                        }
                    }
                    else if (i > 0 || j > 0) {
                        int min = Integer.MAX_VALUE;
                        if (i > 0 && lev[i-1][j] + 1 < min) {
                            min = lev[i-1][j] + 1;
                        }
                        if (j > 0 && lev[i][j-1] + 1 < min) {
                            min = lev[i][j-1] + 1;
                        }
                        if (i > 0 && j > 0 && lev[i-1][j-1] + 1 < min) {
                            min = lev[i-1][j-1] + 1;
                        }
                        lev[i][j] = min;
                    }
                    // 算法校正：levenshtein距离的最小值为两个字符串长度之差
                    lev[i][j] = lev[i][j] < Math.abs(i - j) ? Math.abs(i - j) : lev[i][j];
                }
            }
            // 结果输出
            System.out.println(lev[len1 - 1][len2 - 1]);
        }
    }
}

发表于 2021-09-24 13:40:16 回复(0)

Java

╭(′•o•′)╭☞

java解法
DP:
(1)k1代表替换：
相等 k1 = arr[i-1][i1-1]
不相等 k1 = arr[i-1][i1-1]+1
(2)k2代表删除str1中的这个字符：
k2 = arr[i-1][i1] + 1
(3)k3代表增加str2的这个字符到str1中：
k3 = arr[i][i1-1] + 1
(4)arr[i][i1-1]取k1,k2,k3的最小值
(5)要先把当i=0或者i1=0时，arr[i][i1]的值先填上
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scnner = new Scanner(System.in);
        while(scnner.hasNext()){
            String str1 = scnner.nextLine();
            String str2 = scnner.nextLine();
            int l1 = str1.length();
            int l2 = str2.length();
            str1 = " "+ str1;
            str2 = " "+ str2;
            int[][] arr = new int[l1+1][l2+1]; //记录最长子字符串
            //str1为空时，转换需要的次数
            for (int i = 1; i <= l2; i++) {
                arr[0][i] = i;
            }
            //str2为空时，转换需要的次数
            for (int i = 1; i <= l1; i++) {
                arr[i][0] = i;
            }
            for (int i = 1; i <= l1; i++) {
                for (int i1 = 1; i1 <= l2; i1++) {
                    int k1;
                    if(str1.charAt(i) == str2.charAt(i1)){
                        k1 = arr[i-1][i1-1];
                    }else{
                        k1 = arr[i-1][i1-1] + 1;
                    }
                    int k2 = arr[i-1][i1] + 1; //删除str1[i]
                    int k3 = arr[i][i1-1] + 1; //增加str2[i1]
                    arr[i][i1] = Math.min(k1,k2);
                    arr[i][i1] = Math.min(arr[i][i1],k3);
                }
            }
            System.out.println(arr[l1][l2]);
        }
    }
}

发表于 2021-07-08 19:50:13 回复(1)