Leetcode72. Edit Distance

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

运行效率：

解题思路
二维数组,动态规划法. In the future, I will always see a question where two objects match,Two-dimensional arrays come to mind first,动态规划的办法.

代码如下：

class Solution {
    
  public static int minDistance(String word1, String word2) {
    
        //处理边界条件
        if("".equals(word1)){
    
            return word2.length();
        }
           if("".equals(word2)){
    
            return word1.length();
        }
        //Two-dimensional array dynamic programming method
        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;
            }
        }
        //Initialize the first column of data
        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;
            }
        }
        //Then fill in the others in turn
        for (int row = 1; row < word2.length(); row++) {
    
            for (int col = 1; col < word1.length(); col++) {
    
                int leftObliqueVal = dp[row - 1][col - 1]; //The value of the left slope
                char cc1 = word1.charAt(col);
                char cc2 = word2.charAt(row);
                if (cc1 == cc2) {
    
                    dp[row][col] = leftObliqueVal;
                } else {
    
                    int leftVal = dp[row][col-1]; //positive left value
                    int topVal = dp[row - 1][col];//value directly above
                    dp[row][col] = Math.min(Math.min(leftObliqueVal, leftVal), topVal) + 1;
                }
            }
        }
        return dp[word2.length() - 1][word1.length()-1];
    }
}