题目描述
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:插入一个字符、删除一个字符、替换一个字符。
-示例 1:
-输入:word1 = "horse", word2 = "ros"
-输出:3
-解释:
-horse -> rorse (将 'h' 替换为 'r')
-rorse -> rose (删除 'r')
-rose -> ros (删除 'e')
思路
该题是字符串操作类用动态规划求解的典型题目,类似题目可以见第一篇博文。
- 定义dp的含义——因为word1和word2分别对应两个状态,因此需要使用二维数组。
dp[i][j]代表word1中前i个字符转变为word2中前j个字符所需要的最少操作数。 - 状态转移方程
题目***有三种操作方式:增、删、改,每种操作都对应一个转移方程。
21、增加:当word1的前i个字符和word2的前j-1个字符已经相同后,只需要在word1后增加word2的最后一个字符即可,此时
dp[i][j] = dp[i][j-1] + 1;
22、删除:当word1的前i-1个字符和word2的前j个字符已经相同后,只需要将word1后删除一个字符即可,此时
dp[i][j] = dp[i-1][j] + 1;
33、修改:当word1的前i-1个字符和word2的前j-1个字符已经相同后,只需要修改word1最后一个字符和word2相同即可,此时
dp[i][j] = dp[i-1][j-1] + 1;
34、当word1的前i-1个字符和word2的前j-1个字符已经相同后,且word1第i个字符和word2第j个字符也相同,则不需要操作,此时
dp[i][j] = dp[i-1][j-1];
对于增、删、改三种操作是同一状态下的三种不同情况,因此要取三种情况中的最小值。 - 边界条件
当word1中字符为0时,转换为word2时,需要在word1中添加word2的单词个数,所以要初始化dp[0][i] = i;
当word2中的字符为0时,要从word1转换为word2,需要将word1中字符都删除掉,所以要初始化dp[i][0] = i;
代码
class Solution { public: int minDistance(string word1, string word2) { int len1 = word1.length(), len2 = word2.length(); if(len1 == 0 || len2 == 0) return max(len1, len2); //初始化边界条件 vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0)); for(int i = 0; i <= len1; i++) dp[i][0] = i; for(int i = 0; i <= len2; i++) dp[0][i] = i; //进行状态转移 for(int i = 1; i <= len1; i++) { for(int j = 1; j <= len2; j++) { if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j]= min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1; } } return dp[len1][len2]; } };