给定两个单词 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')
1 #include "_000库函数.h" 2 3 4 //不知道从何下手 5 //参考博客答案 6 7 //要尝试三种操作，因为谁也不知道当前的操作会对后面产生什么样的影响， 8 //那么对于当前比较的两个字符 word1[i] 和 word2[j]，若二者相同，一切好说， 9 //直接跳到下一个位置。若不相同，有三种处理方法，首先是直接插入一个 word2[j]，那么 word2[j] 10 //位置的字符就跳过了，接着比较 word1[i] 和 word2[j + 1] 即可。11 //第二个种方法是删除，即将 word1[i] 字符直接删掉，接着比较 word1[i + 1] 和 word2[j] 即可。12 //第三种则是将 word1[i] 修改为 word2[j]，接着比较 word1[i + 1] 和 word[j + 1] 即可。13 //分析到这里，我们可以直接写出递归的代码，但是很可惜会 Time Limited Exceed，14 //所以我们必须要优化事件复杂度，需要去掉大量的重复计算，15 //这里我们使用记忆数组 memo 来保存计算过的状态，从而可以通过OJ，16 //注意这里的 insertCnt，deleteCnt，replaceCnt 仅仅是表示当前对应的位置分别采用了插入，删除，和替换操作，17 //整体返回的最小距离，后面位置的还是会调用递归返回最小的，参见代码如下：18 class Solution {19 public:20 int minDistance(string word1, string word2) {21 int m = word1.size(), n = word2.size();22 vector > memo(m, vector (n));23 return helper(word1, 0, word2, 0, memo);24 }25 int helper(string& word1, int i, string& word2, int j, vector >& memo) {26 if (i == word1.size()) return (int)word2.size() - j;27 if (j == word2.size()) return (int)word1.size() - i;28 if (memo[i][j] > 0) return memo[i][j];29 int res = 0;30 if (word1[i] == word2[j]) {31 return helper(word1, i + 1, word2, j + 1, memo);32 }33 else {34 int insertCnt = helper(word1, i, word2, j + 1, memo);35 int deleteCnt = helper(word1, i + 1, word2, j, memo);36 int replaceCnt = helper(word1, i + 1, word2, j + 1, memo);37 res = min(insertCnt, min(deleteCnt, replaceCnt)) + 1;38 }39 return memo[i][j] = res;40 }41 };42 43 //根据以往的经验，对于字符串相关的题目且求极值的问题，44 //十有八九都是用动态规划Dynamic Programming来解，这道题也不例外。45 //其实解法一的递归加记忆数组的方法也可以看作是DP的递归写法。46 //这里我们需要维护一个二维的数组dp，其大小为 mxn，m和n分别为 word1 和word2 的长度。47 //dp[i][j] 表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤。那48 //我们可以先给这个二维数组dp的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，49 //于是转换步骤完全是另一个字符串的长度。跟以往的DP题目类似，难点还是在于找出状态转移方程，50 //我们可以举个例子来看，比如word1是“bbc"，word2是”abcd“，那么我们可以得到dp数组如下：51 52 53 //Ø a b c d54 //Ø 0 1 2 3 455 //b 1 1 1 2 356 //b 2 2 1 2 357 //c 3 3 2 1 258 //59 //60 //我们通过观察可以发现，当word1[i] == word2[j]时，dp[i][j] = dp[i - 1][j - 1]，61 //其他情况时，dp[i][j]是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，62 //分别对应的增加，删除，修改操作，具体可以参见解法一种的讲解部分，那么可以得到状态转移方程为：63 //64 //if word1[i - 1] == word2[j - 1]65 // dp[i][j] = dp[i - 1][j - 1] 66 //else67 // min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 68 //69 //70 class Solution {71 public:72 int minDistance(string word1, string word2) {73 int m = word1.size(), n = word2.size();74 vector > dp(m + 1, vector (n + 1));75 for (int i = 0; i <= m; ++i) dp[i][0] = i;76 for (int i = 0; i <= n; ++i) dp[0][i] = i;77 for (int i = 1; i <= m; ++i) {78 for (int j = 1; j <= n; ++j) {79 if (word1[i - 1] == word2[j - 1]) {80 dp[i][j] = dp[i - 1][j - 1];81 }82 else {83 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;84 }85 }86 }87 return dp[m][n];88 }89 };