leetcode--Edit Distance

短命女 2021-10-25 12:40 259阅读 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]; 
        }
    }

转载于:https://www.cnblogs.com/averillzheng/p/3807282.html

发表评论取消回复

表情：

评论列表（有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读

相关 L1distance和L2distance区别

L1distance和L2distance区别： L1distance即曼哈顿，即城市距离，各维度距离之和 L2distance即欧式距离，两点间直线距离参考cs

小鱼儿/ 2022年12月08日 04:21/ 0 赞/ 300 阅读

相关 Raymarching Distance Fields

Raymarching Distance Fields Hello. This is my first article in a series of many, wher

爱被打了一巴掌/ 2022年09月21日 01:38/ 0 赞/ 1 阅读

相关 LeetCode72——Edit Distance

十一月太忙，好一阵没写博客没刷题，现在事情忙完了，生活规律要逐步走入正轨。 \------------------------------------------------

约定不等于承诺〃/ 2022年08月10日 06:16/ 0 赞/ 205 阅读

相关编辑距离Edit distance

http://[blog.csdn.net/pipisorry/article/details/46383947][blog.csdn.net_pipisorry_articl

谁借莪１个温暖的怀抱￠/ 2022年08月05日 04:29/ 0 赞/ 351 阅读

相关 LeetCode - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

左手的ㄟ右手/ 2022年08月04日 12:45/ 0 赞/ 58 阅读

相关 leetcode Edit Distance

题目 Given two words word1 and word2, find the minimum number of steps required to conv

约定不等于承诺〃/ 2022年08月01日 11:18/ 0 赞/ 176 阅读

相关 461_Hamming_Distance

/ The Hamming distance between two integers is the number of positions at whi

た入场券/ 2022年06月08日 00:52/ 0 赞/ 123 阅读

相关 461. Hamming Distance

> Description： The Hamming distance between two integers is the number of positions at

柔情只为你懂/ 2022年05月31日 09:51/ 0 赞/ 180 阅读

相关 leetcode--Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

短命女/ 2021年10月25日 12:40/ 0 赞/ 260 阅读

相关 Leetcode: One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart. 注意这道

╰+哭是因爲堅強的太久メ/ 2021年10月23日 07:15/ 0 赞/ 181 阅读