題目

給你兩個單詞?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')

分析

這是一個經典的動態規劃問題，也叫萊文斯坦距離（Levenshtein distance）。可以使用動態規劃的方法來求解將?word1?轉換成?word2?所使用的最少操作數。

動態規劃

算法思路

定義狀態
設?dp[i][j]?表示將?word1?的前?i?個字符轉換成?word2?的前?j?個字符所需要的最少操作數。這里?i?和?j?的范圍分別是從?0?到?word1.length()?和?word2.length()。

初始化邊界條件

• 當?i = 0?時，意味著?word1?為空字符串，那么將空字符串轉換成?word2?的前?j?個字符需要?j?次插入操作，所以?dp[0][j] = j。
• 當?j = 0?時，意味著?word2?為空字符串，那么將?word1?的前?i?個字符轉換成空字符串需要?i?次刪除操作，所以?dp[i][0] = i。

狀態轉移方程

• 如果?word1[i - 1] == word2[j - 1]，說明當前字符相等，不需要進行額外操作，那么?dp[i][j] = dp[i - 1][j - 1]。
• 如果?word1[i - 1] != word2[j - 1]，則可以進行三種操作：
• 插入操作：要使?word1?的前?i?個字符變成?word2?的前?j?個字符，可以先讓?word1?的前?i?個字符變成?word2?的前?j - 1?個字符，再插入一個字符，即?dp[i][j] = dp[i][j - 1] + 1。
• 刪除操作：先讓?word1?的前?i - 1?個字符變成?word2?的前?j?個字符，再刪除?word1?的第?i?個字符，即?dp[i][j] = dp[i - 1][j] + 1。
• 替換操作：先讓?word1?的前?i - 1?個字符變成?word2?的前?j - 1?個字符，再將?word1?的第?i?個字符替換成?word2?的第?j?個字符，即?dp[i][j] = dp[i - 1][j - 1] + 1。
• 綜合這三種操作，取最小值作為?dp[i][j]?的值，即?dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)。

最終結果
最終結果為?dp[word1.length()][word2.length()]，即把?word1?的全部字符轉換成?word2?的全部字符所需的最少操作數。

時間復雜度：O()，?是?word1?的長度，?為?word2?的長度

空間復雜度：O()

class Solution {
public:int minDistance(std::string word1, std::string word2) {int m = word1.length();int n = word2.length();// 創建 dp 數組std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));// 初始化for (int i = 0; i <= m; ++i) {dp[i][0] = i;}for (int j = 0; j <= n; ++j) {dp[0][j] = j;}// 填充 dp 數組for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = std::min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;}}}return dp[m][n];}
};