力扣-72-编辑距离

public int minDistance(String word1, String word2) {
    if(word1 == null || word2 == null)  return 0;
    char[] w1 = word1.toCharArray();
    char[] w2 = word2.toCharArray();

    int[][] dp = new int[w1.length+1][w2.length+1];//word1前i个字符转换成word2的前j个字符所需要的最少操作

    //base case
    for(int i = 0;i<=w1.length;i++){
        dp[i][0] = i;
    }
    for(int j = 0;j<=w2.length;j++){
        dp[0][j] = j;
    }

    for(int i = 1;i<=w1.length;i++){
        for(int j = 1;j<=w2.length;j++){
            if(w1[i-1] == w2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                //以word1为主,
                //dp[i][j-1]: 插入
                //dp[i-1][j]: 删除
                //dp[i-1][j-1]: 替换
                dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
            }
        }
    }
    return dp[w1.length][w2.length];
}