題目：

鏈接：LeetCode 72. 編輯距離
難度：中等

給你兩個單詞 word1 和 word2， 請返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對一個單詞進行如下三種操作：

• 插入一個字符
• 刪除一個字符
• 替換一個字符

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

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小寫英文字母組成

解題思路：

詳見《Hello 算法》：編輯距離問題

代碼：

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int i = 1; i <= n; i++) dp[i][0] = i; // 插入n個字符的操作數(shù)for (int j = 1; j <= m; j++) dp[0][j] = j;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (word1[i - 1] != word2[j - 1]) {dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; // 對應(yīng)插入、刪除、替換三種操作} else {dp[i][j] = dp[i - 1][j - 1]; // 相同字符不需要操作}}}return dp[n][m];}
};

時間復(fù)雜度O(NM)，空間復(fù)雜度O(NM)。N、M為字符串 word1 和 word2 的長度。