【刷题篇】编辑距离

• 一、题目
• 二、题解

OJ链接

下面这段题目描述是leetcode的官方题目

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

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

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

在这个官方题目描述中，插入、删除和替换一个字符的代价都是1，最后返回最短的编辑距离

我们下面的这段题解是可以给任意指定插入、删除和替换的代价的，最后返回最短的编辑距离

动态规划（样本对应模型）

源码：

public int minDistance1(String word1, String word2,int ac,int dc,int rc) {
        if(word1==null||word2==null){
            return 0;
        }
        char[] str1=word1.toCharArray();
        char[] str2=word2.toCharArray();
        int N= str1.length+1;
        int M= str2.length+1;
        int[][] dp=new int[N][M];
        for (int i = 1; i < N; i++) {
            dp[i][0]=dc*i;
        }
        for (int j = 1; j 
            dp[0][j]=ac*j;
        }
        for (int i = 1; i 
            for (int j = 1; j 
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=dp[i-1][j-1]+rc;
                }
                dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+dc);
                dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+ac);
            }
        }
        return dp[N-1][M-1];
    }
    public int minDistance(String word1, String word2) {
        return minDistance1(word1,word2,1,1,1);
    }