規(guī)劃-5】72.編輯距離)
題目描述給你兩個單詞word1和word2請返回將word1轉(zhuǎn)換成word2所使用的最少操作數(shù)。你可以對一個單詞進(jìn)行如下三種操作插入一個字符刪除一個字符替換一個字符示例 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)解題思路方法一動態(tài)規(guī)劃核心思路狀態(tài)定義dp[i][j] 將word1的前i個字符轉(zhuǎn)換成word2的前j個字符所需的最少操作數(shù)。狀態(tài)轉(zhuǎn)移對于word1[i-1]和word2[j-1]情況1字符相同dp[i][j] dp[i-1][j-1] 不需要操作情況2字符不同dp[i][j] 1 min( dp[i-1][j], // 刪除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替換 word1[i-1] 為 word2[j-1] )初始化dp[0][j] jword1 為空需要插入 j 個字符dp[i][0] iword2 為空需要刪除 i 個字符具體過程示例word1 horse, word2 rosdp: r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] 3 ?代碼實(shí)現(xiàn)寫法1二維 DPclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(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; // 狀態(tài)轉(zhuǎn)移 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] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };寫法2一維 DP空間優(yōu)化class Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(n 1, 0); // 初始化word1 為空 for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 保存 dp[i-1][j-1] dp[0] i; // dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存 dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] 1 min({dp[j], dp[j-1], prev}); } prev temp; // 更新 prev } } return dp[n]; } };復(fù)雜度分析方法時間復(fù)雜度空間復(fù)雜度二維 DPO(m × n)O(m × n)一維 DPO(m × n)O(n)關(guān)鍵細(xì)節(jié)1. 三種操作對應(yīng)哪些狀態(tài)操作狀態(tài)轉(zhuǎn)移含義刪除dp[i-1][j]刪除 word1[i-1] 后用前 i-1 個字符匹配 j 個插入dp[i][j-1]插入 word2[j-1] 后用 i 個字符匹配前 j-1 個替換dp[i-1][j-1]替換 word1[i-1] 為 word2[j-1] 后匹配前 i-1 和前 j-12. 為什么字符相同時不需要操作因?yàn)閣ord1[i-1] word2[j-1]這兩個字符已經(jīng)匹配只需要看前面的部分。3. 一維 DP 的prev變量prev保存的是dp[i-1][j-1]左上角的值因?yàn)閐p[j-1]在當(dāng)前行已經(jīng)被更新了不能直接用?？偨Y(jié)要點(diǎn)說明核心思想dp[i][j]表示轉(zhuǎn)換的最少操作數(shù)狀態(tài)轉(zhuǎn)移相同dp[i-1][j-1]不同1 min(刪, 插, 換)初始化dp[i][0] idp[0][j] j時間復(fù)雜度O(m × n)空間復(fù)雜度O(n) 【動態(tài)規(guī)劃-5】72.編輯距離
題目描述給你兩個單詞word1和word2請返回將word1轉(zhuǎn)換成word2所使用的最少操作數(shù)。你可以對一個單詞進(jìn)行如下三種操作插入一個字符刪除一個字符替換一個字符示例 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)解題思路方法一動態(tài)規(guī)劃核心思路狀態(tài)定義dp[i][j] 將word1的前i個字符轉(zhuǎn)換成word2的前j個字符所需的最少操作數(shù)。狀態(tài)轉(zhuǎn)移對于word1[i-1]和word2[j-1]情況1字符相同dp[i][j] dp[i-1][j-1] 不需要操作情況2字符不同dp[i][j] 1 min( dp[i-1][j], // 刪除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替換 word1[i-1] 為 word2[j-1] )初始化dp[0][j] jword1 為空需要插入 j 個字符dp[i][0] iword2 為空需要刪除 i 個字符具體過程示例word1 horse, word2 rosdp: r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] 3 ?代碼實(shí)現(xiàn)寫法1二維 DPclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(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; // 狀態(tài)轉(zhuǎn)移 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] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };寫法2一維 DP空間優(yōu)化class Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(n 1, 0); // 初始化word1 為空 for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 保存 dp[i-1][j-1] dp[0] i; // dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存 dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] 1 min({dp[j], dp[j-1], prev}); } prev temp; // 更新 prev } } return dp[n]; } };復(fù)雜度分析方法時間復(fù)雜度空間復(fù)雜度二維 DPO(m × n)O(m × n)一維 DPO(m × n)O(n)關(guān)鍵細(xì)節(jié)1. 三種操作對應(yīng)哪些狀態(tài)操作狀態(tài)轉(zhuǎn)移含義刪除dp[i-1][j]刪除 word1[i-1] 后用前 i-1 個字符匹配 j 個插入dp[i][j-1]插入 word2[j-1] 后用 i 個字符匹配前 j-1 個替換dp[i-1][j-1]替換 word1[i-1] 為 word2[j-1] 后匹配前 i-1 和前 j-12. 為什么字符相同時不需要操作因?yàn)閣ord1[i-1] word2[j-1]這兩個字符已經(jīng)匹配只需要看前面的部分。3. 一維 DP 的prev變量prev保存的是dp[i-1][j-1]左上角的值因?yàn)閐p[j-1]在當(dāng)前行已經(jīng)被更新了不能直接用?？偨Y(jié)要點(diǎn)說明核心思想dp[i][j]表示轉(zhuǎn)換的最少操作數(shù)狀態(tài)轉(zhuǎn)移相同dp[i-1][j-1]不同1 min(刪, 插, 換)初始化dp[i][0] idp[0][j] j時間復(fù)雜度O(m × n)空間復(fù)雜度O(n)