力扣72:编辑距离

题目

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

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

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

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

思路

首先我们来解析一下这三种操作本质上是干什么，假设我们有两个字符串A和B。

1. 插入一个字符
   插入一个字符我们可以将其分为对字符串A进行插入和对字符串B进行插入，我们可以发现对A进行插入不就是对B进行删除吗，对B进行插入就是对A进行删除。例如A是“thing”，B是“hing“，我们既可以对A进行删除也可以对B进行插入，这两种操作都可以得到答案所有他们俩是等价的。
2. 删除一个字符
   删除一个字符一样可以分为对A进行删除和对B进行删除，根据上面的结论对A删除就是对B插入，对B删除就是对A进行插入。
3. 替换一个字符
   替换一个字符同样是分为对A进行替换和对B进行替换，这个两个操作就不用多提了同样是等价的，例如A是"thing"，B是"ching”。我们可以将A的t换成c也可以将B的c换成t。

所以上面的三种操作最后我们可以等价于下面三种操作

1. 对A插入一个字符
2. 对B插入一个字符
3. 对A替换一个字符

那么在得到这样的结论之后呢？我们是不是可以把总的问题划分成不同的子问题例如测试用例里的A是“horse”，B是“ros”。我们根据上面的操作发现这个测试用例的答案不就是A是horse，B是ro的答案+1吗，那么这个问题是不是还能继续简化，A是horseB是r，再到A是horseB是空串，再到A是horsB是空串，直到最后A是空串B也是空串。A是空串B是空串的编译距离很好求把那么我们不就可以再从最简化的往前一步一步的求得最初的了吗？
而我们进行的操作又只有上面三种，所以我们想要求得一个字符串到另外一个字符串的编辑距离只要知道在对A进行插入一个字符前的编辑距离，对B进行插入一个字符前的编辑距离，对A进行替换一个字符的编辑距离即可。题目又说是最小的编辑距离所以只要求得这三个距离的最小值当作当前值即可。
这种划分子问题然后从子问题一步一步推导的思想不就是动态规划吗，所以我们定义一个二维数组dp,同时定义i是字符串A的下标，j是字符串B的下标。那么dp[i][j]的意思就是A字符串的前i个字母到B字符串的前j个字母的编辑距离了。通过上面的分析我们可以得到dp[i][j]的状态推导函数是
$$dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]))$$
首先是取这三个值中的最小值这肯定没问题，这三个值分别都是什么意思呢？
dp[i-1][j]对应着第一个操作：对字符串A插入一个字符。
dp[i][j-1]对应着第二个操作：对字符串B插入一个字符。
dp[i-1][j-1]对应着第三个操作：对字符串A替换一个字符。
前两个比较好理解，我们只需要得到操作之前的编辑距离再+1就是操作之后的编辑距离，第三个需要我们提前判断前一个位置的AB字符串字符是不是相同的如果不相同就需要对dp[i-1][j-1]进行++。

代码

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.length();int m = word2.length();// 如果有一个字符串为空串if (n == 0 || m == 0) {return n == 0 ? m : n;}// 动态规划，二维数组，dp[i][j]是word1的第i个位置到word2第j个位置的编译距离vector<vector<int>> dp(n + 1, vector<int>(m + 1));//边界，空串到非空串的编辑距离就是非空串的长度for (int i = 0; i < n + 1; i++) {dp[i][0] = i;}for (int j = 0; j < m + 1; j++) {dp[0][j] = j;}for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {//判断前一个字符是否相同if (word1[i - 1] != word2[j - 1]) {dp[i - 1][j - 1] += 1;}//状态转移方程dp[i][j] = min(dp[i - 1][j] + 1,min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));}}return dp[n][m];}
};