①：暴搜，对于 word1[i] 与 word2[j]，如果二者不相等，有三种方式，即题目所说的那种方式。
优化1：记忆化，每一次都记住到 i，j 位置时已经使用过的次数，如果某一次搜索时，出现已使用次数大于所记录的次数时，可直接return，因为没有意义。
优化2：假设 word1 为长的串，那么答案永远不可能大于 word1.size() - word2.size() + word2.size()，即，先让两者长度相等，再依次使用替换操作。
②：dp[i][j] 表示 word1 的前 i 个变成 word2 的前 j 个所使用的最少次数。那么：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 // 分别对应删操作与增操作
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (word1[i] != word2[j]); // 替换
唯一需要注意的就是初始化的问题：即当 i == 0 与 j == 0 的情况，即前 0 的 dp 值初始化
// 记忆化搜索 class Solution { public: int minDistance(const string &word1, const string &word2) { const string &a = word1.size() < word2.size() ? word2 : word1; const string &b = word1.size() < word2.size() ? word1 : word2; tag.resize(a.size() + 1, vector<int>(b.size() + 1, 1e9)); solve(a, b, 0, 0, 0); return ret; } private: int ret = 1e9; vector<vector<int>> tag; void solve(const string &word1, const string &word2, int i, int j, int cnt) { // 已保证 word1.size() > word2.size() // 那么 cnt 的最大值就是: 删除word1直到二者长度相等, 然后再按 word2.size() 逐个替换 if(cnt > (int)word1.size() - (int)word2.size() + (int)word2.size() || cnt >= ret) return; if(i == word1.size() || j == word2.size()) { if(j != word2.size()) { ret = min(ret, cnt + (int)word2.size() - j); } else { ret = min(ret, cnt + (int)word1.size() - i); } return; } // printf("%d %d %d\n", i, j, cnt); tag[i][j] = min(tag[i][j], cnt); if(word1[i] == word2[j]) { if(tag[i + 1][j + 1] <= cnt) return; solve(word1, word2, i + 1, j + 1, cnt); return; } if(tag[i + 1][j + 1] > cnt + 1) { solve(word1, word2, i + 1, j + 1, cnt + 1); // 替换 } if(tag[i + 1][j] > cnt + 1) { solve(word1, word2, i + 1, j, cnt + 1); // 删除 } if(tag[i][j + 1] > cnt + 1) { solve(word1, word2, i, j + 1, cnt + 1); // 增加 } } };
// dp class Solution { public: int minDistance(const string &word1, const string &word2) { vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 1e9)); for(int i = 0; i <= word1.size(); ++ i) { dp[i][0] = i; } for(int i = 0; i <= word2.size(); ++ i) { dp[0][i] = i; } for(int i = 1; i <= word1.size(); ++ i) { for(int j = 1; j <= word2.size(); ++ j) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (word1[i - 1] != word2[j - 1])); } } return dp.back().back(); } };