题目描述
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
Example2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
解题思路
- 参考这里
- 这里需要维护一个二维的数组 dp，其大小为 mxn，m和n分别为 word1 和 word2 的长度。
- dp[i][j] 表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤。
- 先给这个二维数组 dp 的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，于是转换步骤完全是另一个字符串的长度。
- 跟以往的 DP 题目类似，难点还是在于找出状态转移方程，可以举个例子来看，比如 word1 是 “bbc”，word2 是 “abcd”，可以得到 dp 数组如下：
-
Ø a b c d Ø 0 1 2 3 4 b 1 1 1 2 3 b 2 2 1 2 3 c 3 3 2 1 2 - 通过观察可以发现，当 word1[i] == word2[j] 时，dp[i][j] = dp[i - 1][j - 1]，其他情况时，dp[i][j] 是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，分别对应的增加，删除，修改操作，那么可以得到状态转移方程为：
dp[i][j] = dp[i - 1][j-1] if word1[i - 1] == word2[j - 1] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 else
- 使用dp[i][j]用来表示字符串1的0~i-1、字符串2的0~j-1的最小编辑距离；
- 我们可以知道边界情况：dp[i][0] = i、dp[0][j]=j；
- 同时对于两个字符串的子串，都能分为最后一个字符相等或者不等的情况：
- 如果words[i-1] == words[j-1]：dp[i][j] = dp[i-1][j-1]；也就是说当前的编辑距离和位置i和j的字符无关；
- 如果words[i-1] != words[j-1]：则存在三种可能的操作：
- 向word1插入：dp[i][j] = dp[i][j-1] + 1;
- 从word1删除：dp[i][j] = dp[i-1][j] + 1;
- 替换word1元素：dp[i][j] = dp[i-1][j-1] + 1;
-
从两个字符串的最后的位置开始考虑:
- 如果最后两个字符(i,j)相等，最后两个字符就不要配对，所以等于minDistance(s1[0..i-1]，s2[0…j-1])；
- 如果最后两个字符不相等: 说明要编辑，具体可以分为三种情况:
- 如果 s1[i-1]和s2[j]可以配对，那我就删除s1[i]即可(删除)；
- 如果 s1[i]和s2[j-1]可以配对，那我就在s1的后面加上s2[j]即可(插入)；
- 如果 s1[i-1]和s2[j-1]可以配对，那我就把s1[i]修改成s2[j]即可；
- 接着对于不相同的时候我们的情况比较复杂，我们有三种处理手段，分别是insert、replace和remove。
- 我们先看insert操作。我们insert完之后，也就是word1中的元素会保持不变，而j会向前挪一个位置，也就是 f(i, j) = 1 + f(i, j - 1);
- 接着考虑replace操作，replace会减少word1和word2中一个需要比较的元素（i和j会向前挪一个位置），也就是 f(i,j) = 1 + f(i - 1, j - 1)
- 我们接着考虑最后一个remove操作，这个就很容易了，word1中会减少一个需要比较的元素，而我们j的位置不变，也就是f(i,j) = 1 + f(i - 1, j)。所以我们最后的结果相当三者取最小值即可。
class Solution {
public:
int minDistance(string word1, string word2) {
int row = word1.size();
int col = word2.size();
vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
for(int i = 0; i <= col; i++){ // 初始化
dp[0][i] = i;
}
for(int i = 0; i <= row; i++){
dp[i][0] = i;
}
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++){
if(word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[row][col];
}
};
