題目
給定兩個字符串word1, word2硼控。求出從word1到word2步驟最少的修改方式刘陶，修改方式包括替換(replace)，插入(insert)淀歇，刪除(delete)易核。
- replace: "replace" -> "eeplace"
- insert: "insert" -> "iinsert"
- delete: "delete" ->"elete"
解法
我們使用一個二維數(shù)組dp來記錄從word1到word2的修改步驟，dp[i][j]對應的是從word1[0...i]到word[0...j]
Boundary
從空字符串轉(zhuǎn)換到任意字符串和從任意字符串抓換到空串的操作次數(shù)都為改任意字符串的長度（n次插入或n次刪除）
dp[i][0] = i;
dp[0][j] = j;
Regular
我們使用一個二維數(shù)組dp來記錄從word1到word2的修改步驟浪默，dp[i][j]對應的是從word1[0...i]到word[0...j]牡直，對應每一種修改方式我們都有不同的狀態(tài)轉(zhuǎn)移方程
- replace: dp[i - 1][j - 1] + 1 //保留從word1[0 ... i-1]轉(zhuǎn)變到word2[0 ... j-1]的次數(shù)，再加一纳决，加一指的是本次的修改
- insert: dp[i][j - 1] + 1 // 保留從word1[0 ... i]轉(zhuǎn)變到word2[0 ... j-1]的次數(shù)碰逸，加一
- delete: dp[i - 1][j] + 1// 保留從word1[0 ... i-1]轉(zhuǎn)變到word2[0 ... j]的次數(shù)，加一
對于替換替換還是刪除阔加，我們選其中最小的值
代碼
class Solution {
public:
int minDistance(string word1, string word2) {
int size1 = word1.size(), size2 = word2.size();
vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1, 0));
for (int i = 0; i <= size1; i++) dp[i][0] = i;
for (int j = 0; j <= size2; j++) dp[0][j] = j;
for (int i = 1; i <= size1; i++) {
for (int j = 1; j <= size2; j++) {
int replace = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;
// insert: dp[i][j - 1], which means we use the steps from word1[0..i] to word[0..j]
// delete: dp[i - 1][j], same as the previous one
// and dont forget + 1;
int ins_del = min(dp[i][j - 1], dp[i - 1][j]) + 1;
dp[i][j] = min(replace, ins_del);
}
}
return dp.back().back();
}
};
TODO: Reduce space complexity
