编辑距离--二维动态规划

0x01.问题

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

1. 插入一个字符。
2. 删除一个字符。
3. 替换一个字符。

输入示例：word1 = “horse”, word2 = “ros”
输出示例：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

Java函数形式：    public int minDistance(String word1, String word2) 

注：题目来源于Leetcode

0x02.动态规划三部曲

读完题，发现这是一个经典的动态规划问题的，为什么可以看出来呢？

• 因为两个单词到最后匹配的操作数都与前面的字符有关，所以可以分割成很多子问题来计算，这就是应用动态规划思想的来源。

第一步，寻找状态：

• 因为每次操作都可能与两个单词中任意一个单词相关，所以需要二维的dp来存储。
• 我们可以假定dp[i][j]表示word1的前i个字符组成的字符串变成word2的前j个字符组成的字符串最少需要的操作数。

第二步，寻找状态转移方程：

我们从题目可以得到总共有三种操作，插入，替换，删除，对两个单词来说，也就是有六种状态，但其实有三种是等价的，比如对word1删除一个字符和word2插入一个字符，word1插入一个字符和word2删除一个字符，替换word1中的字符和替换word2的字符。
所以，我们可以得到以下有效的三种操作：

• 修改word1中的字符（与修改word2中的字符等价）
• word1中插入一个字符（与word2中删除一个字符等价）
• word2中插入一个字符（与word1中删除一个字符等价）

我们就可以得到状态方程：

• 如果word1[i-1]=word2[j-1]，那么无需操作，操作数等于上一步，
  dp[i][j=dp[i-1][j-1]。
• 如果不相等，那么操作数应该等于三种操作数里面最小的那种，
  dp[i][j]=min{dp[i-1][j],dp[i-1][j-1],dp[i][j-1]}。

第三步，寻找初始条件：

• 很明显dp[i][0]=i，dp[0][j]=j。

有了上述动态规划的三个步骤，我们就可以开始写代码了。

0x03.解决代码–二维dp

class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length();
        int len2=word2.length();
        if(len1*len2==0) return len1+len2;
        int[][] dp=new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(word1.charAt(i-1)==word2.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-1][j-1],dp[i][j-1]))+1;
            }
        }
        return dp[len1][len2];
    }
}

Leetcode-4.6每日一题打卡完毕！

心情日记：已犯之错，无可挽回，只愿不负有心之人

ATFWUS --Writing By 2020–04-06