题目主要信息

1、给两个字符串str1，str2

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.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int[][] dp = new int[str1.length()+1][str2.length()+1];  //定义动规数组
 
        for(int i=1; i<=str1.length(); i++){  // 初始化
            dp[i][0] = i;
        }
        for(int i=1; i<=str2.length(); i++){  // 初始化
             dp[0][i] = i;
        }
        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); 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, Math.min(dp[i-1][j-1]+1, dp[i][j-1]+1));  //状态转移方程
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}

复杂度分析

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

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

具体方法

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

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int[][] dp = new int[2][str2.length()+1];  //定义动规数组，两行分别表示当前和上一轮的结果，分别为i%2和(i+1)%2

        for(int i=1; i<=str2.length(); i++){  //初始化
            dp[0][i] = i;
        }
        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); j++){
                if(str1.charAt(i-1)==str2.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));
                    }

                }
            }
        }
        return dp[str1.length()%2][str2.length()];
    }
}

复杂度分析

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