给你两个单词 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’)
提示：
- 0 < = w o r d 1. l e n g t h , w o r d 2. l e n g t h < = 500 0 <= word1.length, word2.length <= 500 0<=word1.length,word2.length<=500
- word1 和 word2 由小写英文字母组成
思绪：动态规划
- 字符串 word1 的长度为 n，word2 的长度 为 m
- 定义 f[j] 为将字符串 word1[1…i] 转换为 word[2…j] 所需要的最少操作次数
- 初始时，需要在 word1 和 word2 前面塞一个不存在的 字符，使得下标可以从 1 开始，这样后面就不需要做特别判断
- j = 0时，f[0] 表现将字符串 word[1…i] 转换为空字符串需要的最短操作次数，显然，可以删除全部字符，使其变为空，所以操作次数 f[0] = i
- i = 0时，f[0][j] 表现将字符串 空字符串 转换为 word2[1…j] 需要的最短操作次数，显然，可以每次添加一个字符，使其变为word[1…j]，所以操作次数 f[0][j] = j
- f[j] 的状态转移方程可以进行如下定义：
- 如果 word1 == word[j]，说明它们的末了一个字符相等，不用任何操作，则 f[j] = f[i-1][j-1]，如果 word1 != word[j]，则需要修改word1 的末了一个字符 f[j] = f[i-1][j-1] + 1
- 如果 word1 -> word2[j] 需要添加一个字符，则说明 word1[1…i] == word2[1…j-1] 则 f[j-1] + 1
- 如果 word1 -> word2[j] 需要删除一个字符，则说明 word1[1…i-1] == word2[1…j] 则 f[i-1][j] + 1
- 所以终极 f[j] 取上面几种环境的最小值即可，则有
f[j] = min(f[i-1][j], f[j-1]) + 1;
f[j] = min(f[j], f[i-1][j-1] + (word1 != word2[j]));
- class Solution {
- public:
- int f[510][510];
- int minDistance(string word1, string word2) {
- int n = word1.size(), m = word2.size();
- word1 = "#" + word1, word2 = "#" + word2;
- memset(f, 0x3f, sizeof f);
- for(int i = 0; i <= n; i++) f[i][0] = i;
- for(int j = 0; j <= m; j++) f[0][j] = j;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= m; j++){
- f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
- f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));
- }
- }
- return f[n][m];
- }
- };
|
