计算字符串的编辑距离

经典动态规划，编辑距离问题，dp[i][j]含义为以i - 1结尾的s和以j - 1为结尾的t的最小编辑操作次数，
定义dp[1][1]为s和t的初始位置是便于初始化，dp[0][j] = j和dp[i][0] = i，
否则需要考虑s的第一个字符与遍历t的字符是否相等，t的第一个字符与遍历的s字符是否相等。
两层for循环，当s字符与t字符相等时，dp[i][j] = dp[i - 1][j - 1]相当于既然现在两个字符相等，相当于我直接去掉这两个字符。
若两字符不相等，dp[i][j]为删除i字符即dp[i - 1][j] + 1，删除j字符即dp[i][j - 1] + 1,替换两个字符中的一个dp[i - 1][j - 1] + 1，三者取最小值即可。
遍历结束后，结果为dp[s.length()][t.length()]
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String t = in.nextLine();
            int[][] dp = new int[s.length() + 1][t.length() + 1];
            for (int i = 0; i <= s.length(); i++){
                dp[i][0] = i;
            }
            for (int i = 0; i <= t.length(); i++){
                dp[0][i] = i;
            }
            for (int i = 1; i <= s.length(); i++){
                for (int j = 1; j <= t.length(); j++){
                    if (s.charAt(i - 1) == t.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][j - 1] + 1, dp[i - 1][j - 1] + 1));
                    }
                }
            }
            System.out.println(dp[s.length()][t.length()]);
        }
    }
}

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]);
    }
}

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]);
    }
}

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];
    }
}

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]);
    }
}

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]);
    }
}

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);
    }
}

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()]);
        }
    }
}

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));
        }
    }
}

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;
    }
    
}

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()]);
        }
    }
}

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];
    }
}

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]);
        }
    }
}