首页 > 其他 > 详细

leetcode--Edit Distance

时间:2014-06-25 11:13:59      阅读:344      评论:0      收藏:0      [点我收藏+]

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 class Solution {
   /**
	 * dynamic programming. Very basic problem.
	 * @param word1 -String 
	 * @param word2 -String
	 * @return  int -number of modifications to change word1 to word2
	 * @author Averill Zheng
	 * @version 2014-06-24
	 * @since JDK 1.7
	 */
	public int minDistance(String word1, String word2) {
		int column = word1.length(), row = word2.length();
		if(row == 0)
			return column;
		if(column == 0)
			return row;
		int[][] changes = new int[row + 1][column + 1];
		for(int i = 0; i < column + 1; ++i)
			changes[0][i] = i;
		for(int i = 0; i < row + 1; ++i)
			changes[i][0] = i;
		for(int i = 1; i < row + 1; ++i){
			for(int j = 1; j < column + 1; ++j){
				if(word1.charAt(j - 1) == word2.charAt(i - 1))
					changes[i][j] = Math.min(changes[i - 1][j - 1], 1 + Math.min(changes[i - 1][j], 
							changes[i][j - 1]));
				else
					changes[i][j] = Math.min(1 + changes[i - 1][j - 1], 1 + Math.min(changes[i - 1][j], 
							changes[i][j - 1]));
			}
		}
	    return changes[row][column]; 
    }
}

  

leetcode--Edit Distance,布布扣,bubuko.com

leetcode--Edit Distance

原文:http://www.cnblogs.com/averillzheng/p/3807282.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!