编辑距离

2021-03-11

72. 编辑距离

难度困难

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

动态规划

dp[i][j]代表第一个字符串的第i个字符到第二个字符串的第j个字符时，不相同的字符的数量

如果字符串1中的第i个字符与字符串2中的第j个字符不相同时，有三种情况（此时需要选择种操作的最小值）：
- dp[i-1][j]+1代表第一个字符串删除一个字符
- dp[i][j-1]+1代表第一个字符串插入一个字符
- dp[i-1][j-1]+1代表第一个字符串替换了一个字符
如果字符串中的两个字符相同时，不需要处理
- 直接是dp[i][j] = dp[i-1][j-1]

转移方程的设置

如果当前的两个字符串的字符不相同，那么最小值应当是dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
如果当前的两个字符串的字符相同，那么最小值应当是dp[i][j] = dp[i-1][j-1]
边界条件是假设另外的一个字符串为空时，不同的数量dp[i][0]=i,dp[0][j]=j，下标从1开始

记录编辑过程

package leetcode;

public class EditDistancePro {
    public static void main(String[] args) {
        EditDistancePro p =new EditDistancePro();

        System.out.println(p.minDistance("horse","ros"));
    }

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] f = new int[m + 1][n + 1];
		// 当字符串2为空时，字符串1里面的所有字符都要删除
        for (int i = 1; i <= m; i++) {
            f[i][0] = i;
        }
		// 当字符串1为空时，字符串1要插入字符串2中的每一个字符
        for (int j = 1; j <= n; j++) {
            f[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
            	// 如果当前遍历的两个字符不相同
            	// dp[i-1][j]+1 表示第一个字符串删除第i个字符
            	// dp[i][j-1]+1 表示第一个字符串插入一个字符，插入的字符是第二个字符串的第j个字符
            	// dp[i-1][j-1]+1 表示第一个字符串中的第i-1个字符替换成第二个字符串的第j-1个字符
				// 当前f[i][j]的修改次数取决于前面的子问题的最小值
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    f[i][j] = Math.min(Math.min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
                } else {
                	// 如果字符相同,那么不做任何操作
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
		// 输出编辑过程
        int i = m, j = n;
        String[] op = new String[m+1];
        while (i > 0 && j > 0) {
            if (f[i][j] == f[i - 1][j - 1]) {
                op[i] = "不做变动";
                i--;
                j--;
            } else if (f[i][j] == f[i - 1][j] + 1) {
                op[i] = "删除了一个字符\t"+word1.charAt(i);
                i--;
            } else if (f[i][j] == f[i][j - 1] + 1) {
                op[i] = "插入了一个字符\t"+word1.charAt(j);
                j--;
            } else if (f[i][j] == f[i - 1][j - 1] + 1) {
                op[i] = "替换了一个字符\t"+word1.charAt(i-1)+"->"+word2.charAt(j-1);
                i--;
                j--;
            }
        }

        for (i = 0; i < m; i++) {
            System.out.println(op[i]);
        }

        return f[m][n];
    }
}

不记录编辑过程

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        if(m*n==0)return m+n;

        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(word1.charAt(i-1)!=word2.charAt(j-1)){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

参考文献
详解一道经典面试题：编辑距离
 最小编辑距离 — 解析及python实现