首页 > 代码库 > LeetCode - 72. Edit Distance
LeetCode - 72. 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
参考：https://segmentfault.com/a/1190000003741294
import java.util.*;public class Solution { public int minDistance(String word1, String word2) { if (word1 == null && word2 == null) return 0; int len1 = word1.length(); int len2 = word2.length(); if (len1 == 0) return len2; if (len2 == 0) return len1; int[][] dp = new int[len1+1][len2+1]; for (int i=0; i<=len1; i++) dp[i][0] = i; for (int j=0; j<=len2; j++) dp[0][j] = j; for (int i=1; i<=len1; i++) { for (int j=1; j<=len2; j++) { int insert = dp[i][j-1] + 1; int delete = dp[i-1][j] + 1; int replace = dp[i-1][j-1] + (word1.charAt(i-1)==word2.charAt(j-1)?0:1); dp[i][j] = Math.min(insert, Math.min(delete, replace)); } } return dp[len1][len2]; }}
LeetCode - 72. Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。