72. 编辑距离
题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
思路分析
最小编辑距离，使用动态规划求解，关于该问题的具体解答，可参看夜深人静写算法（二十二）- 最小编辑距离，这个系列对于动态规划总结的相当不错。设定dp[i] [j]表示word1的前i个字符转变为word2的前j个字符所需的最小操作数。分为以下三种情况：
(1) 插入。假设dp[i] [j-1]已知，即word1前i个字符转变为word2前j-1个字符所需操作数已知，那么在word1[i]后面插入word2[j]就可以.dp[i] [j]=dp[i] [j-1]+1.
(2) 删除。 假设dp[i-1] [j]已知，即word1前i-1个字符转变为word2前j个字符所需操作数已知，那么删除word1[i]即可。dp[i] [j]=dp[i-1] [j]+1。
(3)替换。假设dp[i-1] [j-1]已知，即word1前i-1个字符转变为word2前j-1个字符所需操作数已知，那么把word1[i]替换成word2[j]即可，但是当word1[i-1]word2[j-1]的时候，不需要替换。dp[i] [j]=dp[i-1] [j-1]，word1[i-1]word2[j-1]。dp[i] [j]=dp[i-1] [j-1]+1，word1[i-1]!=word2[j-1]。
边界问题：
当i0&&j0,即空串变为空串，dp[i] [j]=0;
当i==0&&j>0,即空串变为j个字符的字符串，那么需要一直插入,dp[i] [j]=dp[i] [j-1]+1
当i>0&&j==0,即i个字符的字符串变为空串，那么需要一直删除,dp[i] [j]=dp[i-1] [j]+1
注意本题i,j代表的不是下标，因此dp[0] [0]表示空串，不是第一个字符的比较。
代码实现
class Solution {
public:
int minDistance(string word1, string word2) {
int len1=word1.size(),len2=word2.size();
vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
for(int i=0;i<=len1;i++)
{
for(int j=0;j<=len2;j++)
{
//一直插入
if(i==0&&j>0)
dp[i][j]=dp[i][j-1]+1;
else if(j==0&&i>0) //一直删除
dp[i][j]=dp[i-1][j]+1;
else if(i==0&&j==0) //空串变成空串
dp[i][j]=0;
else
{
//先比较插入和删除
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
//在判断字符是否相等
if(word1[i-1]==word2[j-1])
{
//相等那么不需要操作
dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
}
else
{
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
}
}
}
return dp[len1][len2];
}
};