题解 | 编辑距离(一)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        //用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，
        // 那很明显dp[str1.length][str2.length]就是我们要求的编辑距离
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 1; i <= str1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= str2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    //如果两个相同，则直接继承过来
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //如果不同，则有三种情况
                    //1,新增一个，因为新增的一定相同,所以和j-1的时候的数量一致,对应的是dp[i][j - 1]
                    //2,删除一个, 把当前的值删除,对应的是dp[i - 1][j]
                    //3.修改一个,修改的一定相同，所以值为各退一步，对应的是dp[i - 1][j-1]
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return  dp[str1.length()][str2.length()];
    }
}