LeetCode 72. Edit Distance
LeetCode题解专栏：LeetCode题解 LeetCode 所有题目总结：LeetCode 所有题目总结 大部分题目C++，Python，Java的解法都有。
此题链接：Edit Distance - LeetCode LeetCode 动态规划（Dynamic programming）系列题目:LeetCode 动态规划（Dynamic programming）系列题目 做这道题目前建议先做One Edit Distance - LeetCode 文章地址:LeetCode 161. One Edit Distance–Python,Java,C++解法 - zhangpeterx的博客 - 博客
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a characterDelete a characterReplace a characterExample 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')这道题目是hard难度的，做法肯定是动态规划，至于怎么做就很难想了。 具体做法官方的结题文章写得很好：Edit Distance - LeetCode Articles
评论区里的大佬们发表了看法：
tomasnovella: Reaaaaally ? You guys don’t even mention in the solution that it’s a good old Levenshtein distance ? Please if you use some known algorithm, at least mention it!
所以这道题目的英文正式名字叫做Levenshtein Distance Algorithm
Java官方解法如下：
class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); // if one of the strings is empty if (n * m == 0) return n + m; // array to store the convertion history int [][] d = new int[n + 1][m + 1]; // init boundaries for (int i = 0; i < n + 1; i++) { d[i][0] = i; } for (int j = 0; j < m + 1; j++) { d[0][j] = j; } // DP compute for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { int left = d[i - 1][j] + 1; int down = d[i][j - 1] + 1; int left_down = d[i - 1][j - 1]; if (word1.charAt(i - 1) != word2.charAt(j - 1)) left_down += 1; d[i][j] = Math.min(left, Math.min(down, left_down)); } } return d[n][m]; } }Python官方解法如下：
class Solution: def minDistance(self, word1: str, word2: str) -> int: n = len(word1) m = len(word2) # if one of the strings is empty if n * m == 0: return n + m # array to store the convertion history d = [ [0] * (m + 1) for _ in range(n + 1)] # init boundaries for i in range(n + 1): d[i][0] = i for j in range(m + 1): d[0][j] = j # DP compute for i in range(1, n + 1): for j in range(1, m + 1): left = d[i - 1][j] + 1 down = d[i][j - 1] + 1 left_down = d[i - 1][j - 1] if word1[i - 1] != word2[j - 1]: left_down += 1 d[i][j] = min(left, down, left_down) return d[n][m]