Leetcode72. 编辑距离

题目传送地址：https://leetcode.cn/problems/edit-distance/

运行效率：

解题思路
二维数组，动态规划法。 以后凡是看到两个对象匹配的题，首先想到二维数组，动态规划的办法。

代码如下：

class Solution {
    
  public static int minDistance(String word1, String word2) {
    
        //处理边界条件
        if("".equals(word1)){
    
            return word2.length();
        }
           if("".equals(word2)){
    
            return word1.length();
        }
        //二维数组动态规划法
        int[][] dp = new int[word2.length()][word1.length()];
        char c1 = word1.charAt(0);
        char c2 = word2.charAt(0);
        //初始化第一行的数据
        for (int col = 0; col < word1.length(); col++) {
    
            String substring = word1.substring(0, col + 1);
            if (substring.indexOf(c2) != -1) {
    
                dp[0][col] = col;
            } else {
    
                dp[0][col] = col+1;
            }
        }
        //初始化第一列的数据
        for (int row = 0; row < word2.length(); row++) {
    
            String substring = word2.substring(0, row + 1);
            if (substring.indexOf(c1) != -1) {
    
                dp[row][0] = row;
            } else {
    
                dp[row][0] = row + 1;
            }
        }
        //然后再依次填充其他
        for (int row = 1; row < word2.length(); row++) {
    
            for (int col = 1; col < word1.length(); col++) {
    
                int leftObliqueVal = dp[row - 1][col - 1]; //左斜方的值
                char cc1 = word1.charAt(col);
                char cc2 = word2.charAt(row);
                if (cc1 == cc2) {
    
                    dp[row][col] = leftObliqueVal;
                } else {
    
                    int leftVal = dp[row][col-1]; //正左边的值
                    int topVal = dp[row - 1][col];//正上方的值
                    dp[row][col] = Math.min(Math.min(leftObliqueVal, leftVal), topVal) + 1;
                }
            }
        }
        return dp[word2.length() - 1][word1.length()-1];
    }
}