LintCode-编辑距离
编辑 距离 lintcode
2023-09-14 09:09:02 时间
给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法:
- 插入一个字符
- 删除一个字符
- 替换一个字符
您在真实的面试中是否遇到过这个题?
Yes
例子
标签 Expand 给出 work1="mart" 和 work2="karma"
返回 3
相关题目 Expand
分析:经典的动态规划面试题。在有道的实习面中遇到过,用dp[i][j]表示第一个字符串到i第二个字符串到j的时候须要进行多少次改动。
代码:
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 n = word1.length(); int m = word2.length(); vector<vector<int> > dp(n+1,vector<int>(m+1,0)); for(int i = 1;i<=n;i++) dp[i][0]=i; for(int i=1;i<=m;i++) dp[0][i]=i; for(int i=1;i<=n;i++) { char c1 = word1[i-1]; for(int j=1;j<=m;j++) { char c2 = word2[j-1]; if(c1==c2) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1; } } return dp[n][m]; } };
相关文章
- Cockos Reaper mac(数字音频编辑制作软件)
- 怎么退出vi编辑界面_centos保存退出vim
- 路径匹配之编辑距离ED算法
- Acrobat安装激活(可编辑的PDF),包括Windows+mac全版本
- 最小编辑距离
- zGallery for Mac(图片查看编辑工具)
- WordPress 6.2 发布,全面提升站点编辑体验
- VEGAS Pro 19下载_VEGAS Pro(视频编辑)软件安装包下载附安装教程
- Linux VIM编辑技巧: 快速上手(linuxvim怎么编辑)
- Linux下调节命令:掌握超级能力(linux下编辑命令)
- Linux之美:优秀的图片编辑工具推荐(linuxpic)
- Linux工具:使用PDF文件管理和编辑功能(linux工具pdf)
- CSSvista可同时在IE和Fifrefox调试的CSS编辑提供下载