LintCode-编辑距离
2024-09-26 23:24:14
题目描述:
给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法:
- 插入一个字符
- 删除一个字符
- 替换一个字符
样例
给出 work1="mart" 和 work2="karma"
返回 3
public class Solution {
/**
* @param word1 & word2: Two string.
* @return: The minimum number of steps.
*/
public int minDistance(String word1, String word2) {
// write your code here
int[][] dp = new int[word1.length()+1][word2.length()+1]; for(int i=1;i<=word1.length();i++)
dp[i][0] = i; for(int i=1;i<=word2.length();i++)
dp[0][i] = i; for(int i=0;i<word1.length();i++){
for(int j=0;j<word2.length();j++){
if(word1.charAt(i) == word2.charAt(j)){
dp[i+1][j+1] = Math.min(dp[i][j],Math.min(dp[i][j+1],dp[i+1][j])+1);
}else{
dp[i+1][j+1] = Math.min(dp[i][j+1]+1,Math.min(dp[i][j],dp[i+1][j])+1);
}
}
}
return dp[word1.length()][word2.length()];
}
}
最新文章
- 51nod1072(wythoff 博弈)
- Android延时执行的几种方法
- 浅析jQuery(function(){})与(function(){})(jQuery)之间的区别
- java并发编程-Executor框架
- redis的lua使用(EVALSHA)
- SQL语句基础之 管理数据库,表 和 数据
- 333. Largest BST Subtree
- LeetCode #3. Longest Substring Without Repeating Characters C#
- nlog学习使用
- unity 快速创建小地图
- 关于elk中filebeat定义好日志输出,但是redis里面却没有输出内容的问题
- sscanf(),sscanf_s()的相关用法
- 查阅JDK,collection与collections区别大
- egg.js连接和使用Mongodb
- 【问题记录】centos 开机启动命令未执行
- SEO优化上首页之搜索引擎原理内容处理与索引
- ubuntu修改固定ip
- Spring中使用JDBC
- ADV拍卖
- Linpack之HPCG测试
热门文章
- 部署SharePoint2013解决方案
- 存储过程获取新插入记录ID
- python 备份脚本
- php install extension
- javaTemplates-学习笔记一
- jquery不限图片焦点图
- Kate Spade_百度百科
- sharepoint 2013 文档库 资源管理器打开报错 在文件资源管理器中打开此位置时遇到问题,将此网站添加到受信任站点列表,然后重试。
- .net mvc System.Web.Optimization 、System.Data.Entity.Infrastructure找不到
- Android数据的四种存储方式SharedPreferences、SQLite、Content Provider和File (二) —— SQLite