NC35 编辑距离(二)

题目链接：https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4

题目描述

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

数据范围：0 ≤ |str1|,|str2| ≤ 5000，0 < ic,dc,rc ≤ 10000

要求：空间复杂度 O(n)，时间复杂度 O(n^2)

示例 1：

输入："abc","adc",5,3,2
返回值：2

示例 2：

输入："abc","adc",5,3,100
返回值：8

解题代码

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();
        int len2 = str2.length();
        //dp[i][j]不包含第i个字符和第j个字符，因此需要+1
        int[][] dp = new int[len1 + 1][len2 + 1];
        //矩阵第一行表示空字符串转为str2的代价，插入j个字符
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = j * ic;
        }
        //矩阵第1列表示str1转为空字符串的代价，删除i个字符
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i * dc;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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][j - 1] + ic, dp[i - 1][j] + dc);
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + rc);
                }
            }
        }
        return dp[len1][len2];
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2022/09/05 16:43:03