题目描写叙述:
给定一个源串和目标串。可以对源串进行例如以下操作:
1. 在给定位置上插入一个字符
2. 替换随意字符
3. 删除随意字符
写一个程序。返回最小操作数,使得对源串进行这些操作后等于目标串,源串和目标串的长度都小于2000。
思路:
设状态dp[i][j] 表示从源串s[0...i] 和 目标串t[0...j] 的最短编辑距离
边界为:dp[i][0] = i,dp[0][j] = j
递推方程:
- 假设s[i] == t[j], 那么 dp[i][j] = dp[i-1][j-1]
- 假设s[i] != t[j],那么有三种操作情况:
class Solution {
public:
int minDistance(string word1, string word2) {
int Slen = word1.size();
int Tlen = word2.size();
int dp[Slen+1][Tlen+1] = {0};//注意:这里都+1,而且初始化为0
//长度为n的字符串有n+1个隔板
for(int i=1; i<=Slen; i++) //注意从1開始
dp[i][0] = i;
for(int j=1; j<=Tlen; j++)
dp[0][j] = j;
for(int i=1; i<=Slen; i++)
{
for(int j=1; j<=Tlen; j++)
{
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
{
int temp = min(dp[i-1][j], dp[i][j-1]);
dp[i][j] = min(temp, dp[i-1][j-1]) + 1;
}
}
}
return dp[Slen][Tlen];
}
};
行编辑距离Edit Distance——动态规划的更多相关文章
-
利用编辑距离(Edit Distance)计算两个字符串的相似度
利用编辑距离(Edit Distance)计算两个字符串的相似度 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.许可 ...
-
编辑距离——Edit Distance
编辑距离 在计算机科学中,编辑距离是一种量化两个字符串差异程度的方法,也就是计算从一个字符串转换成另外一个字符串所需要的最少操作步骤.不同的编辑距离中定义了不同操作的集合.比较常用的莱温斯坦距离(Le ...
-
[Leetcode 72]编辑距离 Edit Distance
[题目] Given two words word1 and word2, find the minimum number of operations required to convert word ...
-
[Swift]LeetCode72. 编辑距离 | Edit Distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to ...
-
Edit Distance(动态规划,难)
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2 ...
-
编辑距离Edit Distance 非常典型的DP类型题目
https://leetcode.com/problems/edit-distance/?tab=Description 真的非常好,也非常典型. https://discuss.leetcode.c ...
-
动态规划 求解 Minimum Edit Distance
http://blog.csdn.net/abcjennifer/article/details/7735272 自然语言处理(NLP)中,有一个基本问题就是求两个字符串的minimal Edit D ...
-
leetCode 72.Edit Distance (编辑距离) 解题思路和方法
Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert ...
-
Leetcode之动态规划(DP)专题-72. 编辑距离(Edit Distance)
Leetcode之动态规划(DP)专题-72. 编辑距离(Edit Distance) 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 . 你可 ...
随机推荐
-
Java线程并发中常见的锁
随着互联网的蓬勃发展,越来越多的互联网企业面临着用户量膨胀而带来的并发安全问题.本文着重介绍了在java并发中常见的几种锁机制. 1.偏向锁 偏向锁是JDK1.6提出来的一种锁优化的机制.其核心的思想 ...
-
sql 、linq、lambda 查询语句的区别
LINQ的书写格式如下: from 临时变量 in 集合对象或数据库对象 where 条件表达式 [order by条件] select 临时变量中被查询的值 [group by 条件] Lambda ...
-
Storm累计求和进群运行代码
打成jar包放在主节点上去运行. import java.util.Map; import backtype.storm.Config; import backtype.storm.StormSubm ...
-
Python使用subprocess的Popen要调用系统命令
当我们须要调用系统的命令的时候,最先考虑的os模块.用os.system()和os.popen()来进行操作.可是这两个命令过于简单.不能完毕一些复杂的操作,如给执行的命令提供输入或者读取命令的输出, ...
-
接近带给你AngularJS - 经验说明示例
接近带给你AngularJS列: 带你走近AngularJS - 基本功能介绍 带你走近AngularJS - 体验指令实例 带你走近AngularJS - 创建自己定义指令 ------------ ...
-
js基础和工具库
/* * 作者: 胡乐 * 2015/4/18 * js 基础 和 工具库 * * * */ //根据获取对象 function hGetId(id){ return document.getElem ...
-
关于在jsp页面中使用/struts-tags标签库的迭代器时,从ValueStack获取参数使用EL的问题
情况复原下: 通过valuestack存了个user,然后页面里可以${user.sex}拿到男.${user.sex=='男'}拿到ture 但是在使用 <s:if text="${ ...
-
[Java]数组排序-选择排序 冒泡排序 插入排序
1 选择排序 原理:a 将数组中的每个元素,与第一个元素比较 如果这个元素小于第一个元素, 就将这个 两个元素交换. b 每轮使用a的规则, 可以选择出 ...
-
cocos2dx-lua 圆角矩形 圆角图片 drawNode
使用的官方类是:drawNode 函数是:drawNode:drawPolygon() C++函数的参数说明: //画多边形,verts为点集,count为点数,fillColor为填充颜色,bord ...
-
Codeforces 986C AND Graph dfs
原文链接https://www.cnblogs.com/zhouzhendong/p/9161514.html 题目传送门 - Codeforces 986C 题意 给定 $n,m (0\leq n\ ...