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

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 len1 = str1.length(); // 获取 str1 的长度
        int len2 = str2.length(); // 获取 str2 的长度
        
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // 别忘了进行初始化
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { // 如果在当前位置上， str1 和 str2 的字符相等，那么 dp[i][j] = dp[i - 1][j - 1]。原因是不再需要变化
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else { // 如果当前位置上，str1 和 str2 的字符不相等，那么就有可能通过三种情况进行变换
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
}