Leetcode 72 Edit Distance DP好题
Leetcode 72 Edit Distance DP好题
triplebee
发布于 2018-01-12 15:00:34
发布于 2018-01-12 15:00:34
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:
a) Insert a character b) Delete a character c) Replace a character
求用插入、删除、替换三种操作将字符串a变成字符串b的最小步数。
dp[i][j]表示a的前i个字符变为b的前j个字符需要的最少步数。
先初始化边界情况 dp[i][0]和dp[0][i]，
当判断的两位相同时，不需要做任何操作，所以
dp[i][j]=dp[i-1][j-1];而当两位不同时，需要找出三种操作中操作较小的一种。
从dp[i-1][j]转移过来是用了删除，相当于i这位没有了；
从dp[i][j-1]转移过来是用了插入，相当于j这位是新添加的；
从dp[i-1][j-1]转移过来是用了替换；
所以合并起来是这样的：
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;class Solution {
public:
int minDistance(string word1, string word2) {
vector<int> temp(word2.size()+1,0);
vector<vector<int>> dp(word1.size()+1,temp);
for(int i=0;i<=word1.size();i++) dp[i][0]=i;
for(int i=0;i<=word2.size();i++) dp[0][i]=i;
for(int i=1;i<=word1.size();i++)
{
for(int j=1;j<=word2.size();j++)
{
if(word1[i-1]==word2[j-1])
dp[i][j]=dp[i-1][j-1];
else
{
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
return dp[word1.size()][word2.size()];
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-09-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读