?LeetCode刷題實戰(zhàn)72：編輯距離
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?編輯距離，我們先來看題面：
https://leetcode-cn.com/problems/edit-distance
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
題意
插入一個字符
刪除一個字符
替換一個字符
示例?1：
輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (將 'h'?替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
示例?2：
輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (刪除 't')
inention -> enention (將 'i'?替換為 'e')
enention -> exention (將 'n'?替換為 'x')
exention -> exection (將 'n'?替換為 'c')
exection -> execution (插入 'u')
解題
使用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;
class?Solution?{
public:
????int?minDistance(string?word1, string?word2)?{
????????int?rows = word1.length();
????????int?cols = word2.length();
????????vector<vector<int> > dp(rows+1, vector<int>(cols+1, 0));
????????for(int?i=1; i<=rows; ++i)
????????????dp[i][0] = i;
????????for(int?j=1; j<=cols; ++j)
????????????dp[0][j] = j;
????????for(int?i=1; i<=rows; ++i){
????????????for(int?j=1; j<=cols; ++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-1][j], dp[i][j-1])) + 1;
????????????}
????????}
????????return?dp[rows][cols];
????}
};
上期推文：