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

基本思路：

设start1和start2 为word1和word2的待比较位置，初始为0,0

那么：
如果word1.charAt(start1)==word2.charAt(start2)时，继续求minDistance(word.subString(start1+1,start2+1));
如果不等于则分六种情况
*1、在word1的start1前面插入和word2的start2处的相等字符，然后求1+minDistance(word.subString(start1,start2+1))
* 2、在word2的start2前面插入和word1的start1处的相等字符，然后求1+minDistance(word.subString(start1+1,start2))
* 3、删除word1的start1处的字符，然后求1+minDistance(word.subString(start1+1,start2))
* 4、删除word2的start2处的字符，然后求1+minDistance(word.subString(start1,start2+1))
* 5、更换word1的start1处为word2的start2处的字符，然后求1+minDistance(word.subString(start1+1,start2+1))
* 6、更换word2的start2处为word1的start1处的字符，然后求1+minDistance(word.subString(start1+1,start2+1))
   最后求这六种情况中最小的值

下面是递归做法：（重复步骤多，太耗时）

	public int minDistance(String word1, String word2)
	{
		return getMin(word1, 0, word1.length()-1, word2,0, word2.length()-1);
	}
	
	public int getMin(String word1, int start1,int end1,String word2,int start2,int end2)
	{
		if(start1>end1)
		{
			if(start2>end2)
				return 0;
			else
				return end2-start2+1;
		}
		if(start2>end2)
		{
			if(start1>end1)
				return 0;
			else
				return end1-start1+1;
		}
		
		if(word1.charAt(start1)==word2.charAt(start2))
			return getMin(word1, start1+1, end1, word2, start2+1, end2);
		else
		{
			int one = 0;
			int two = 0;
			int three = 0;
			one = 1+getMin(word1, start1+1, end1, word2, start2+1, end2);
			two = 1+getMin(word1, start1+1, end1, word2, start2, end2);
			three = 1+getMin(word1, start1, end1, word2, start2+1, end2);
			return Math.min(one, Math.min(two, three));
		}
	}

	public int minDistance(String word1, String word2)
	{
		int[][] rs = new int[word1.length()+1][word2.length()+1];
		
		//初始化
		for(int i = word1.length();i>=0;i--)
			rs[i][word2.length()] = word1.length()-i;
		for(int i = word2.length();i>=0;i--)
			rs[word1.length()][i] = word2.length()-i;
		
		for(int i = word1.length()-1;i>=0;i--)
		{
			for(int j = word2.length()-1;j>=0;j--)
			{
				if(word1.charAt(i)==word2.charAt(j))
					rs[i][j] = rs[i+1][j+1];
				else
					rs[i][j] = Math.min(rs[i+1][j+1], Math.min(rs[i+1][j], rs[i][j+1]))+1;
			}
		}
		return rs[0][0];
	}

Edit Distance,布布扣,bubuko.com

Edit Distance

原文：http://blog.csdn.net/cow__sky/article/details/21989571