lintcode:最小编辑距离

最小编辑距离

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例

给出 work1="mart" 和 work2="karma"

返回 3

解题

动态规划解题

定义矩阵dp[][]

dp[i][j] 表示word1前i个字符 [0,1,2,...,i-1] 和 word2前j个字符 [0,1,2,...,j-1]的编辑距离

lintcode:最小编辑距离

ch1 = word1.charAt(i)

ch2 = word2.charAt(j)

当 ch1== ch2:word1[0--(i-1)] 与word2[0--(j-1)] 的编辑距离dp[i][j] = dp[i-1][j-1] 不需要修改

当ch1!=ch2: 有三种修改方式

  •       ch1替换word2中的ch2,此时的编辑距离受上一位的编辑距离影响, 编辑距离是:dp[i-1][j-1] + 1
  • ch2插入到word1中ch1的前面,word1中的ch2还没有比较,编辑距离是:dp[i-1][j] + 1
  • 删除ch2 编辑距离:dp[i][j-1] + 1

选取上面的最小值更新dp[i][j]的值

Java程序定义的dp矩阵长度是len1 + 1 * len2 + 1 的和上面有一点区别

import java.util.Scanner;
// write your code here
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
Main m = new Main();
while(in.hasNext()){
String[] str = in.nextLine().split(" ");
String word1 = str[0];
String word2 = str[1];
int min = m.minDistance(word1,word2);
System.out.println(min);
}
}
public int minDistance(String word1,String word2){
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i =0;i<=len1;i++){
dp[i][0] = i;
}
for(int j =0;j<= len2;j++){
dp[0][j] = j;
}
for(int i =0;i< len1;i++){
char ch1 = word1.charAt(i);
for(int j =0;j< len2;j++){
char ch2 = word2.charAt(j);
if(ch1 == ch2){
dp[i+1][j+1] = dp[i][j];
}else{
int replace = dp[i][j] +1;// ch1 代替 ch2
int insert = dp[i][j+1] + 1;// ch2 插入到 ch1 前面的位置
int delete = dp[i+1][j] + 1;// 删除ch2
int min =replace>insert?insert:replace;
min = min>delete?delete:min;
dp[i+1][j+1] = min;
}
}
}
return dp[len1][len2];
}
}

注:搜狐2016实习笔试题目

上一篇:Java入门:一些初学者需要掌握的基础算法程序——二分查找


下一篇:Vim实用小技巧