lintcode-119-编辑距离
2024-08-31 21:05:40
119-编辑距离
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
- 插入一个字符
- 删除一个字符
- 替换一个字符
样例
给出 work1="mart" 和 work2="karma"
返回 3标签
字符串处理 动态规划
思路
使用动态规划，用二维数组dp[i][j]表示第一个字符串到i第二个字符串到j的时候需要进行多少次修改
动态转移方程为：
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] （S[i]==T[j]）
dp[i][j] = dp[i-1][j] （S[i]!=T[j]）
过程如下：
code
class Solution {
public:
/**
* @param word1 & word2: Two string.
* @return: The minimum number of steps.
*/
int minDistance(string word1, string word2) {
// write your code here
int size1 = word1.size(), size2 = word2.size(),i = 0, j = 0;
if(size1 <= 0 ) {
return size2;
}
else if(size2 <= 0) {
return size1;
}
vector<vector<int> > dp(size1+1, vector<int>(size2+1, 0));
for(i=1; i<=size1; i++) {
dp[i][0]= i;
}
for(i=1; i<=size2; i++) {
dp[0][i] = i;
}
for(i=1; i<=size1; i++) {
for(j=1; j<=size2; j++) {
if(word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = findMin(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;
}
}
}
return dp[size1][size2];
}
int findMin(int num1, int num2, int num3) {
int min = num1 > num2 ? num2 : num1;
return min > num3 ? num3 : min;
}
};
最新文章
- js中函数的一些理论知识
- [CareerCup] 18.1 Add Two Numbers 两数相加
- grains
- opencv2-新特性及Mat
- Iterator中hasNext(), next() 和ResultSet结果集的next方法的区别
- ASP.NET 5系列教程 (六): 在 MVC6 中创建 Web API
- 比较几种工具Python(x,y) Anaconda WinPython
- iOS简易柱状图(带动画)--新手入门篇
- windows7旗舰版激活密钥永久版免费分享
- Python实现kMeans(k均值聚类)
- NOIP2006 作业调度方案
- StarSpace是用于高效学习实体向量的通用神经模型
- Linux常用命令(第二版) --压缩解压缩命令
- 进入Docker容器的4种方式
- 普林斯顿微积分读本 大纲与重点 （by zzd）
- 根据IP查地理位置信息
- Debug的使用
- git解决冲突（rebase版）
- 查找nginx安装的路径以及相关安装操作命令
- Python写一个根据日期计算是星期几的模块