LeetCode题解——Edit Distance_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > LeetCode题解——Edit Distance

LeetCode题解——Edit Distance

 2014/8/23 15:17:15  Mir_Tempo  程序员俱乐部  我要评论(0)
  • 摘要:Giventwowordsword1andword2,findtheminimumnumberofstepsrequiredtoconvertword1toword2.(eachoperationiscountedas1step.)Youhavethefollowing3operationspermittedonaword:a)Insertacharacterb)Deleteacharacterc)Replaceacharacter分析:本题用动态规划的思想解答
  • 标签:
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

分析:本题用动态规划的思想解答。用二维数组p[i][[j]表示word1[1...i]变为word2[1...j]需要经过最少的步数。若已知p[i][j]要p[i+1][j+1]对应3种操作,有三种转化方式
1. 修改一个字符。
当word1[i+1] != word2[j+1]时,需要修改字符,而word1[1…i]变换到word2[1...j]已经求得为p[i][j], 因此修改字符时,p[i+1][j+1] = p[i][j] + (word1[i+1] == word2[j+1]? 0:1)
2. 插入一个字符。
插入一个字符是在将word1[1...i+1]变换到word2[1...j]的基础上,插入一个字符使得word1[1...i+1]变换到word2[1....j+1],因此p[i+1][j+1] = p[i+1][j]+1;
3. 删除一个字符
需要删除时,说明字符word1[i+1]是多余的,删除后的字符串结果与将word1[1...i]变换到word2[1...j+1]相同,只是多了一步操作。因此p[i+1][j+1] = p[i][j+1]+1

p[i+1][j+1]取这三种变换的最小值。

所以
  p[i][j] = min(p[i-1][j-1] +(word1[i] == word2[j] ? 0 :1), min(p[i][j-1] +1, p[i-1][j] +1) )

初始化:
p[0][j] 表示将空字符串转化成word2[1...j],因此 p[0][j] = j
p[i][0] 表示将word1[1…i]转化成空字符串,因此p[i][0] = i

算法复杂度O(mn)
代码:

class="java">public class Edit_Distance {
	public int minDistance(String word1, String word2) {
		
		int p[][] = new int[word1.length()+1][word2.length()+1];
		for(int i=0;i<p[0].length;++i)
			p[0][i] = i;
		for(int i=0;i<p.length;++i)
			p[i][0] = i;
		for(int i=1;i<=word1.length();++i){
			for(int j=1;j<=word2.length();++j){
				p[i][j] = Math.min(p[i][j-1]+1, Math.min(p[i-1][j]+1, p[i-1][j-1]+(word1.charAt(i-1)== word2.charAt(j-1)? 0: 1)));
			}
		}
		return  p[word1.length()][word2.length()];
	}
	
}


  • 相关文章
发表评论
用户名: 匿名