[leetcode]Edit Distance

新博文地址：[leetcode]Edit distance

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

 这道题在编程之美上有原题，书中给出的答案是用 递归版实现，代码如下：

 

	public int minDistanceWithRecurse(String word1, String word2) {
		if(word1.length() == 0){
			return word2.length();
		}
		if(word2.length() == 0){
			return word1.length();
		}
		if(word1.charAt(0) == word2.charAt(0)){
			return minDistance(word1.substring(1), word2.substring(1));
		}else{
			int t1 = minDistance(word1.substring(1), word2);
			int t2 = minDistance(word1, word2.substring(1));
			int t3 = minDistance(word1.substring(1), word2.substring(1));
			return Math.min(t1, Math.min(t2, t3)) + 1;
		}
	}

 但是坑爹的超时了，后来想了一下，还是不会，google之，发现原来Edit Distance是自然语言处理中的很重要的一个算法，而且自成一脉。大家可以去看下维奇百科的解释，Edit Distance中明确的说明了这个问题用递归实现的复杂度是指数级的，因此，采用了DP解决思路：百科中已经讲得很明白了。这里就简单的小结一下：

 

维护一个二维矩阵来记录distance的状态：
dinstance[i][j]分别表示字符串word1[0~i]与word2[0~j]的距离
这里需要将distance开到[word1.length() +1][word2.length() + 1]

其中[0][0]表示二者都为空串时，distance显然为0.
当i = 0时，distance[0][j] = j （其中 1 <= j <= word2.length()），同理
当j = 0时，distance[i][0] = i （其中 1 <= i <= word1.length()）

而distance[i][j]有两种情况
当word1.charAt(i) == word2.charAt(j)时，
显然distance[i][j] = distance[i-1][j - 1];
当word1.charAt(i) != word2.charAt(j)时，
需要考察distance[i - 1][j - 1]、 distance[i][j - 1]、distance[i - 1][j]分别对应了三种情况：修改word1[i] 为word2[j]、删除word2[j]、删除word1[i]，找到这三者中最小的一个数 ，然后+ 1（表示删除操作或者修改操作）

 具体的还需要看这里：

代码如下：

public int minDistance(String word1, String word2) {
		int length1 = word1.length();
		int length2 = word2.length();
		if(length1 == 0 || length2 == 0){
			return length1 == 0? length2: length1;
		}
		int[][] distance = new int[length1 + 1][length2 + 1];
		distance[0][0] = 0;
		for(int i = 1; i <= length1; i++){
			distance[i][0] = i ;
		}
		for(int i = 1; i <= length2; i++){
			distance[0][i] = i ;
		}
		for(int i = 1; i <= length1; i++){
			for(int j = 1; j <= length2; j++){
				if(word1.charAt(i-1) == word2.charAt(j-1)){
					distance[i][j] = distance[i - 1][j - 1];
				}else{
					distance[i][j] = Math.min(distance[i - 1][j - 1], Math.min(distance[i][j - 1], distance[i - 1][j])) + 1;
				}
			}
		}
		return distance[length1][length2];
	}

 

 

评论

1 楼 249326109 2014-06-27  

这题目分析的真好。