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

import java.util.*;


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

        // 初始化,当其中一个字符串为空时，只需其中一个字符串增加或删除对应位置字符即可，此时编辑距离+1
        for(int i = 1;i <= str1.length();i++){
            dp[i][0] = dp[i - 1][0] + 1;
        }

        for(int j = 1;j <= str2.length();j++){
            dp[0][j] = dp[0][j - 1] + 1;
        }

        // 状态转移：当str[i]和str2[j]字符相等时，则不需要编辑，编辑距离为dp[i - 1][j - 1]。否则最小编辑距离取决于由dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]经过编辑后的最小编辑距离
        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{
                    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()];
    }
}