Problem: Given two strings of size m, n and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
两个一维表的C++实现:
int editDisDP(string s1, string s2)
{
vector<vector<int> > ta(2, vector<int>(s2.size()+1));
bool flag = false;
for (int i = 0; i <= s2.size(); i++)
{
ta[!flag][i] = i;
}
for (int i = 0; i < s1.size(); i++)
{
ta[flag][0] = ta[!flag][0]+1;
for (int j = 0; j < s2.size(); j++)
{
if (s1[i] == s2[j])
{
ta[flag][j+1] = ta[!flag][j];
}
else
{
ta[flag][j+1] = min(min(ta[!flag][j+1], ta[flag][j]),
ta[!flag][j]) + 1;
}
}
flag = !flag;
}
return ta[!flag][s2.size()];
}
分享到:
相关推荐
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
geeks_algorithms 极客算法编码问题
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
欢迎来到4Geeks学院 <\编码时间>内容关于。创始人。团队。奖项。校友关于4Geeks是一家大公司,感觉就像一家小公司;每个人都可以访问,我们喜欢与人接触,我们相信量身定制的教育,而不会离开您的工作,并且100%...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
Geeks for Geeks的DSA练习: :
本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好...
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
geek极客们都用什么神器,这篇文章给了你答案。
Mac OS X For Unix Geeks 2003
自从我们意识到人工智能如何对市场产生积极影响以来,几乎每个大型企业都在寻找人工智能专业人士来帮助他们实现愿景。在这个人工智能面试问题博客中,我收集了面试官最常问的问题。...3. 人工智能场景面试题
Ubuntu for Non-Geeks (Fourth Edition)
Cooking.for.Geeks, hope all programer have good food
A HashMap for Geeks and normal programmers.