​LeetCode刷題實戰72:編輯距離

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從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

題意給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

插入一個字符

刪除一個字符

替換一個字符

示例 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')

解題https://blog.csdn.net/Koala_Tree/article/details/80074722

使用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];
    }
};

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。