题解 | #NC35 最小编辑代价#

与力扣 72. 编辑距离 类似

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[][] dp = new int[str1.length() + 1][str2.length() + 1];
        // str1 ==> str2（str2 不能修改）
        //第一列代表将 str1 全部删除
        for (int i = 0; i < dp.length; i++) dp[i][0] = i * dc;
        //第一行代表 不断添加字符到 str1，直到和 str2 相同
        for (int i = 0; i < dp[0].length; i++) dp[0][i] = i * ic;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) 
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    //替换
                    int replace = dp[i - 1][j - 1] + rc;
                    //按行走要删
                    int delete = dp[i - 1][j] + dc;
                    //按列要加
                    int insert = dp[i][j - 1] + ic;
                    //取最小
                    dp[i][j] = Math.min(replace, Math.min(delete, insert));
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}