力扣：72. 编辑距离

力扣：72. 编辑距离

题目：
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

解析：

一样的，首先dp数组的含义直接为题目的目的即0 ~ i 转换成0 ~ j 所需要的最小操作数。

当前值相等：

• 只需要将0~ i-1 转换成0~j-1即可。即dp[i][j] = dp[i-1][j-1];

当前值不相等（要到达目的有三种方式）：

• 插入元素才能转换成目标字符串：即：dp[i][j] = dp[i][j - 1] + 1;因为转换成标准字符串肯定是插入word2【j】这个字母，换个角度来想只需要 0~ i 实现0~ j-1 然后+1（即插入这个值的操作）即可。
• 删除元素才能转换成目标字符串：即dp[i][j] = dp[i - 1][j] + 1;
• 修改元素才能转换成目标字符串：dp[i][j] = dp[i - 1][j - 1] + 1;将word1当前值修改为word2当前值。

初始化：
按照含义，递归公式，模拟遍历来初始化。此时按照含义即可初始化完成。

 for(int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
        for(int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
1
2

代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
        for(int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
        for(int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
        for(int i = 1; i <= word1.size(); ++i) {
            for(int j = 1; j <= word2.size(); ++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]+1,dp[i-1][j-1]+1));
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15