题解 | #编辑距离(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int m = str1.length(),n = str2.length();
        dp[m][n] = 0;
        for(int j = 0;j<n;j++){
            dp[m][j] = n-j;
        }
        for(int i = 0;i<m;i++){
            dp[i][n] = m-i;
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i][j] = dp[i+1][j+1];
                }else{
                    dp[i][j] = Math.min(dp[i+1][j+1],Math.min(dp[i+1][j],dp[i][j+1]))+1;
                }
            }
        }
        return dp[0][0];
        
    }
    
}