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

import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // 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 * dc;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j * ic;
        }
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 如果在当前位置上，str1 和 str2 的字符相等，那么不需要进行任何操作，dp[i][j] = dp[i - 1][j - 1]
                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] + rc, Math.min(dp[i - 1][j] + dc, dp[i][j - 1] + ic));
                }
            }
        }
        return dp[len1][len2];
    }
}