字符串的编辑距离,又称为Levenshtein距离。是利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括:
例如对于"hello"和"hell",可以通过插入一个'o'和删除一个'o'来达到目的。
一般来说,两个字符的编辑距离越小,则它们越相似。如果两个字符串相同,则它们的编辑距离为0.可以分析出,两个字符串的编辑距离肯定不超过它们的最大长度(可以通过先把短串的每一位都修改成长串对应位置的字符,然后插入长串中的剩下字符。)
问题描述:
给定两个字符串A和B,求字符串A至少经过多少步字符操作变成字符串B。
问题分析:
(1)首先考虑A串的第一个字符
假设存在两个字符串A和B,长度分别为lenA和lenB。首先考虑第一个字符,如果是一样的,所以只需要计算A[2……lenA]和B[2……lenB]之间的距离即可。那么如果两个字符串的第一个字符不一样的话,那么要考虑把第一个字符变成一样的:
- 修改A串的第一个字符成B串的第一个字符,之后只需要计算A[2……lenA]和B[2……lenB]之间的距离即可;
- 删除A串的第一个字符,之后只需要计算A[2……lenA]和B[1……lenB]之间的距离即可;
- 把B串的第一个字符插入到A串的第一个字符之前,之后仅需要计算A[1……lenA]和B[2……lenB]的距离即可。
(2)接下来只需要考虑A串的第i个字符和B串的第j个字符。
这个时候我们不考虑A的前i-1个字符和B的第j-1个字符。如果A串的第i个字符和B的第j个字符相等,即A[i]=B[j],则只需要计算A[i+1……lenA]和B[j+1……lenB]之间的距离即可。如果不想等,则:
- 修改A的第i个字符为B的第j个字符,之后仅需要计算A[i+1……lenA]和B[j+1……lenB]之间的距离即可;
- 删除A的第i个字符,之后只需要计算A[i+1……lenA]和B[j……lenB]之间的距离即可;
- 把B串的第j个字符插入到A串的第i个字符之前,之后仅需要计算A[i.....lenA]和B[j+1......lenB]之间的距离即可。
构建动态规划方程:
用dp[i][j]表示A串从第i个字符开始和B串第j个字符开始的距离。则从上面的分析,不难推导出动态规划方法:
代码如下:
public class 字符串编辑距离 {
public static int editDistance(String source,String target){
int len1=source.length();
int len2=target.length();
//第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离
int[][] dp=new int[len1][len2];
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=1;i<len1;i++){
for(int j=1;j<len2;j++){
int addOp=dp[i][j-1]+1;
int delOp=dp[i-1][j]+1;
int changeOp=dp[i-1][j-1]+(source.charAt(i-1)==target.charAt(j-1)?0:1);
dp[i][j]=Math.min(Math.min(addOp, delOp), changeOp);
}
}
return dp[len1-1][len2-1];
}
public static void main(String[] args){
String source="sailn";
String target="failing";
System.out.println(editDistance(source, target));
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)