Leetcode 72 Edit Distance DP好题
发布时间：2020-12-13 21:15:25 所属栏目：PHP教程 来源：网络整理
导读：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 charac
|
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 求用插入、删除、替换3种操作将字符串a变成字符串b的最小步数。 dp[i][j]表示a的前i个字符变成b的前j个字符需要的最少步数。先初始化边界情况 dp[i][0]和dp[0][i]， 当判断的两位相同时，不需要做任何操作，所以 dp[i][j]=dp[i⑴][j⑴]; 而当两位不同时，需要找出3种操作中操作较小的1种。
从dp[i⑴][j]转移过来是用了删除，相当于i这位没有了； 从dp[i][j⑴]转移过来是用了插入，相当于j这位是新添加的； 从dp[i⑴][j⑴]转移过来是用了替换； 所以合并起来是这样的： dp[i][j]=min(min(dp[i⑴][j],dp[i][j⑴]),dp[i⑴][j⑴])+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⑴]==word2[j⑴])
dp[i][j]=dp[i⑴][j⑴];
else
{
dp[i][j]=min(min(dp[i⑴][j],dp[i⑴][j⑴])+1;
}
}
}
return dp[word1.size()][word2.size()];
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |