来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance

1.题目

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

---

• 示例 1：
  输入：word1 = "horse", word2 = "ros"
  输出：3

• 解释：
  horse -> rorse (将 'h' 替换为 'r')
  rorse -> rose (删除 'r')
  rose -> ros (删除 'e')

• 示例 2：
  输入：word1 = "intention", word2 = "execution"
  输出：5

• 解释：
  intention -> inention (删除 't')
  inention -> enention (将 'i' 替换为 'e')
  enention -> exention (将 'n' 替换为 'x')
  exention -> exection (将 'n' 替换为 'c')
  exection -> execution (插入 'u')

---

 public int minDistance(String word1, String word2) {


}

2.JAVA代码

动态规划，时间复杂度O(NM)，空间复杂度O(NM)

时间复杂度O(N*M)，空间复杂度O(N*M)

public static int minDistance(String word1, String word2) {
        int word1Len = word1.length();
        int word2Len = word2.length();
        if(word1Len==0||word2Len==0){
            return word1Len==0?word2Len:word1Len;
        }
        /***
         * [主程序-动态规划]：
         *  i==0:
         *      dp[i][j] = j
         *      当word1为""时，编辑距离为word2的长度
         *  j==0:
         *      dp[i][j] = i
         *      当word2为""时，编辑距离为word1的长度
         *  i!=0 && j!=0:
         *      word1[i]==word2[j]:
         *          dp[i][j] = dp[i-1][j-1]
         *      word1[i]!=word2[j]:
         *          dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
         */
        int[][] dp =new int[word1Len+1][word2Len+1];
        for(int i=0;i<word1Len+1;i++){
            for(int j=0;j<word2Len+1;j++){
                if(i==0){
                    dp[i][j]=j;
                }else if(j==0){
                    dp[i][j]=i;
                }
            }
        }
        for(int i=1;i<word1Len+1;i++){
            for(int j=1;j<word2Len+1;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1]);
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1])+1;
                }
            }
        }
        return dp[word1Len][word2Len];

    }