国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > Leetcode 72 Edit Distance DP好题

Leetcode 72 Edit Distance DP好题

来源:程序员人生   发布时间:2016-10-12 09:43:54 阅读次数:955次

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

求用插入、删除、替换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⑴]),dp[i⑴][j⑴])+1; } } } return dp[word1.size()][word2.size()]; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生