题目主要信息

1、给出若干组字符串，每一组包括两个

2、每个字符串可以通过替换、增添、删除来进行修改，每次修改需要1次编辑距离

3、求最小编辑距离使得两个字符串相等

方法一:字符串比较

具体方法

编辑距离是一类非常经典的动态规划的题目。 我们使用dp[i][j]表示字符串A的前i个字符与字符串B的前j个字符相同所需要的编辑距离。 首先需要进行状态的初始化，当一个字符串为空时，编辑距离等于另一个字符串的长度 对于状态转移方程，需要分两种情况讨论： 第一种情况，a[i]==b[j]，这种情况下，我们不需要进行编辑，dp[i][j]=dp[i-1][j-1] 第二种情况，a[i]!=b[j]，如果两个字符不相等，我们有三种处理方式：替换字符串b，编辑距离为dp[i-1][j-1]+1；插入一个字符与其相等，则编辑距离为dp[i-1][j]+1；删除该字符，编辑距离为dp[i][j-1]+1，三者取其小即可。 具体以下图为例

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String a = sc.nextLine();
            String b = sc.nextLine();
            int[][] dp = new int[a.length()+1][b.length()+1];  //定义动规数组

            for(int i=1; i<=a.length(); i++){  // 初始化
                dp[i][0] = i;
            }
            for(int i=1; i<=b.length(); i++){  // 初始化
                dp[0][i] = i;
            }
            for(int i=1; i<=a.length(); i++){
                for(int j=1; j<=b.length(); 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-1]+1, dp[i][j-1]+1));  //状态转移方程
                    }
                }
            }
            System.out.println(dp[a.length()][b.length()]);
        }
    }
}

复杂度分析

• 时间复杂度：$O(mn)O(mn)$，其中m和n分别为两个字符串的长度
• 空间复杂度：$O(mn)O(mn)$，辅助数组为二维数组

方法二：动态规划（空间压缩）

具体方法

在状态转移方程中我们可以看到，长度为i的字符串的编辑距离，只和长度为i-1或长度为i的字符串相关，因此可以使用两个一维数组替代二维数组，实现空间压缩，两个一维数组分别表示长度为i时的编辑距离和i-1时的编辑距离。

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String a = sc.nextLine();
            String b = sc.nextLine();
            int[][] dp = new int[2][b.length()+1];  //定义动规数组，两行分别表示当前和上一轮的结果，分别为i%2和(i+1)%2

            for(int i=1; i<=b.length(); i++){  //初始化
                dp[0][i] = i;
            }
            for(int i=1; i<=a.length(); i++){
                for(int j=1; j<=b.length(); j++){
                    if(a.charAt(i-1)==b.charAt(j-1)){  //第一种情况
                        if(j-1==0){
                            dp[i%2][j] = i-1; 
                        }else{
                            dp[i%2][j] = dp[(i+1)%2][j-1];
                        }

                    }else{  //第二种情况
                        if(j-1==0){
                            dp[i%2][j] = Math.min(dp[(i+1)%2][j]+1, i);
                        }else{
                            dp[i%2][j] = Math.min(dp[(i+1)%2][j]+1, Math.min(dp[(i+1)%2][j-1]+1, dp[i%2][j-1]+1));
                        }

                    }
                }
            }
            System.out.println(dp[a.length()%2][b.length()]);
        }
    }
}

复杂度分析

• 时间复杂度：$O(mn)O(mn)$，其中m和n分别为两个字符串的长度
• 空间复杂度：$O(n)O(n)$