leetcode第一刷_Edit Distance
2024-09-01 09:32:15
最小编辑距离。非常经典的问题。今年微软实习生的笔试有一个这个的扩展版,牵扯到模板之类的,当时一行代码也没写出来。
。
dp能够非常优雅的解决问题。状态转移方程也非常明白。用pos[i][j]表示word1的前i个字符与word2的前j个字符之间的编辑距离。假设word[i-1]与word[j-1]相等,那pos[i][j]与pos[i-1][j-1]相等,否则的话。依据编辑的几种操作。能够从三种情况中选代替价最小的一种。从word1中删除一个字符?从word2中删除一个字符?改动当中一个?边界也非常easy,一个字符串长度为0时。编辑距离一定是依据还有一个的长度不断添加的。
写成代码一目了然:
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.length(), len2 = word2.length();
int pos[len1+1][len2+1];
for(int i=0;i<=len1;i++)
pos[i][0] = i;
for(int i=0;i<=len2;i++)
pos[0][i] = i;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(word1[i-1] == word2[j-1])
pos[i][j] = pos[i-1][j-1];
else{
pos[i][j] = min(pos[i-1][j], min(pos[i-1][j-1], pos[i][j-1]))+1;
}
}
}
return pos[len1][len2];
}
};
最新文章
- iOS中 将 颜色转化成图片
- 自定义NSLog
- BZOJ-1491 社交网络 FLoyd+乱搞
- 还原ORACLE DUMP 的值
- Open vSwitch简述
- php array函数实例应用
- [Tips]解决HG之waiting for lock on repository
- ffmpeg之YUYV转RGB ARM使用流程分析
- F - Rain on your Parade - hdu 2389(二分图匹配,Hk算法)
- 用MarkDown来排版写作
- CATransform3D参数的意义
- c# 借助cmd命令解析apk文件信息
- 1.3. chromium源代码分析 - chromiumframe - 窗口系列
- sizeof,终极无惑(上)
- hdu 4090 GemAnd Prince
- Linux内核探索之路&mdash;&mdash;关于方法
- IIS URLReWrite URL 重写模块 下载地址
- String的replaceAll()用法详解
- Cocos2dx源码赏析(4)之Action动作
- MyBatis 总结记录