（一）72. Edit Distance
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 character Delete a character Replace a character Example 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')
参考：https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)
- 这道题代码和64. Minimum Path Sum非常相似，但是分析起来更难
- 两者的分析方式相似：都是找到通解，然后再去求特解；并且都是首先初始化一行一列，然后再遍历找最小值
- 对于字符串word1和word2，定义f(i,j)表示实现word1的前i个字符和word2的前j个字符相等需要的最小步骤
- 如果word1第i个和word2第j个相同，那么不需要进行操作，即f(i,j) = f(i-1,j-1)
- 如果不同，那么需要进行替换、删除、增加操作则f(i,j) = min(f(i-1,j-1),f(i-1,j),f(i,j-1)) + 1
- 总的来说步骤是1.设置初始值（第一行第一列） 2. 遍历数组，得到每一个点的最小值
package DynamicProgramming.EditDistance;
public class Solution {
public static int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] cost = new int[len1+1][len2+1];
for(int i=1; i <= len1; i++){ //初始化第一列
cost[i][0] = i;
}
for(int i=1; i <= len2; i++){ //初始化第一行
cost[0][i] = i;
}
for(int i=1; i <= len1; i++){
for(int j=1; j <= len2; j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
cost[i][j] = cost[i-1][j-1];
} else{
cost[i][j] = findMin(cost[i-1][j-1],cost[i-1][j],cost[i][j-1]);
cost[i][j] += 1;
}
}
}
return cost[len1][len2];
}
public static int findMin(int a, int b, int c){ //找到三个数中的最小值
int min = a < b ? a : b;
min = min < c ? min : c;
return min;
}
public static void main(String[] args){
String word1 = "horse";
String word2 = "ros";
System.out.println(minDistance(word1,word2));
}
}