Edit Distance

最后更新于:2022-04-01 22:57:13

**一. 题目描述** Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2\. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: Insert a character  Delete a character  Replace a character **二. 题目分析** 给定两个字符串word1和word2,算出讲word1转化成word2所需的最少编辑操作次数。允许的编辑操作包括以下三种: 将一个字符替换成另一个字符  在字符串中插入一个字符  删除字符串中的一个字符 例如将A(abc)转成B(acbc): 你可选择以下操作:  acc (b→c)替换  acb (c→b)替换  acbc (→c)插入 这不是最少编辑次数,因为其实只需要删除第二个字符`c`就可以了,这样只需操作一次。 使用`i`表示字符串`word1`的下标(从下标1开始),使用`j`表示字符串`word2`的下标。 用`k[i][j]`来表示`word1[1, ... , i]`到`word2[1, ... , j]`之间的最少编辑操作数。则有以下规律: ~~~ k[i][0] = i; k[0][j] = j; k[i][j] = k[i - 1][j - 1] (if word1[i] == word2[j]) k[i][j] = min(k[i - 1][j - 1], k[i][j - 1], k[i - 1][j]) + 1 (if word1[i] != word2[j]) ~~~ **三. 示例代码** ~~~ #include #include #include using namespace std; class Solution { public: int minDistance(const string &word1, const string &word2) { const size_t m = word1.size() + 1; const size_t n = word2.size() + 1; vector > k(m, vector(n)); for (size_t i = 0; i < m; ++i) k[i][0] = i; for (size_t j = 0; j < n; ++j) k[0][j] = j; for (size_t i = 1; i < m; ++i) { for (size_t j = 1; j < n; ++j) { if (word1[i - 1] == word2[j - 1]) k[i][j] = k[i - 1][j - 1]; else k[i][j] = min(k[i - 1][j - 1], min(k[i - 1][j], k[i][j - 1])) + 1; } } return k[m - 1][n - 1]; } }; ~~~ ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5f0b9ec2.jpg) **四. 小结** 动态规划的经典题目,要快速写出状态转移方程还是有点难度的。
';