注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex72 Edit Distance  

2015-05-29 23:20:30|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


这一题虽然能想到要用动态规划,可是死活推不出公式,貌似这是一个自然语言理解领域一个比较常见的算法。

自然语言处理(NLP)中,有一个基本问题就是求两个字符串的minimal Edit Distance, 也称Levenshtein distance。受到一篇Edit Distance介绍文章的启发,本文用动态规划求取了两个字符串之间的minimal Edit Distance. 动态规划方程将在下文进行讲解。 


1. what is minimal edit distance?

简单地说,就是仅通过插入(insert)、删除(delete)和替换(substitute)个操作将一个字符串s1变换到另一个字符串s2的最少步骤数。熟悉算法的同学很容易知道这是个动态规划问题。 

其实一个替换操作可以相当于一个delete+一个insert,所以我们将权值定义如下:

I  (insert):1

D (delete):1

S (substitute):2


2. example:

intention->execution

Minimal edit distance:

delete i ; n->e ; t->x ; insert c ; n->u 求和得cost=8


我表示不懂额~~不过有公式的话,貌似都是很简单的说,参考中第一个代码简洁,最后一个有图有真相,就不盗图了。

class Solution {
public:
/*
* 这些题目都好难啊~~~~
* DP Formulation: D[i,j]=min(D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+flag);//其中if(s1[i]!=s2[j])则flag=2,else flag=0;
* D[i,j]: the minimal edit distance for s1的前i个字符和 s2的前j个字符
*/
int minDistance(string word1, string word2) {
int len1 = word1.length();
int len2 = word2.length();
if (len1 == 0) return len2;
if (len2 == 0) return len1;
vector<vector<int> > dp(len1 + 1, vector<int>(len2 + 1));

for (int i = 0; i <= len1; ++i) dp[i][0] = i;
for (int j = 0; j <= len2; ++j) dp[0][j] = j;

int cost;
for (int i = 1; i <= len1; ++i)
{
for (int j = 1; j <= len2; ++j)
{
cost = (word1[i - 1] == word2[j - 1]) ? 0 : 1;
dp[i][j] = min(dp[i - 1][j - 1] + cost, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
}
}
return dp[len1][len2];
}
};


参考
http://www.cnblogs.com/easonliu/p/3661537.html
http://blog.csdn.net/abcjennifer/article/details/7735272
http://blog.csdn.net/beiyetengqing/article/details/8105180
http://www.cnblogs.com/chuanlong/archive/2013/04/01/2993774.html
http://blog.csdn.net/huaweidong2011/article/details/7727482
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017