动态规划实现编辑距离的计算

编辑距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
由于这个概念是俄罗斯科学家Vladimir Levenshtein在1965年提出的,因此编辑距离又称为Levenshtein Distance。这个是典型的动态规划问题,只要求出状态转移方程就很好解决了。
首先定义一个函数getDistance(String s1, String s2, int i, int j) i和j分别为字符串s1和s2的长度。我们列出状态转移方程(参考链接戳这里

editdistance

public class EditDistance {
	public static void main(String args[]){
		String s1 = "student";
		String s2 = "study";
		System.out.println(getDistance(s1, s2, s1.length(), s2.length()));
	}

	public static int getDistance(String s1, String s2, int i, int j){
        if (i == 0 && j == 0){
        	return 0;
        }else if (i == 0 && j > 0){
        	return j;
        }else if (i > 0 && j == 0){
        	return i;
        }else {
        	int flag = 0;
        	if(s1.charAt(i-1)!=s2.charAt(j-1))
        		flag = 1;
			return min(getDistance(s1, s2, i-1, j)+1, getDistance(s1, s2, i, j-1)+1, getDistance(s1, s2, i-1, j-1)+flag);
		}
	}
	
	public static int min(int a,int b,int c){
		int min = a>b ? b : a;
		return min>c ? c : min;
	}
}

大致就是这样子了,不过还是感觉不是特别完美,等有空了思考下交换怎么玩吧。

——Snake

snake

作者: snake

我们需要为这个社会做一点贡献,失去了才懂得去珍惜。

《动态规划实现编辑距离的计算》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注