最小编辑代价

题目描述

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

示例1

输入

复制

"abc","adc",5,3,2

返回值

复制

2

示例2

输入

复制

"abc","adc",5,3,100

返回值

复制

8

备注:

$1 \leq |str_1|, |str_2| \leq 5000$
$1 \leq ic, dc, rc \leq 10000$

动态规划

import java.util.*;

public class Solution {

    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        
        int m = str1.length();
        int n = str2.length();
        
        int [][]dp = new int[m+1][n+1];
        
        // 注意当第二个字符串为空时，第一个字符串需要完全删除
        for(int i=1;i<=m;i++){
            dp[i][0] = i*dc;
        }
        // 注意当第一个字符串为空时，第一个字符串需要插入和第二个字符串相同的内容
        for(int j=1;j<=n;j++){
            dp[0][j] = j*ic;
        }
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    // dp[i][j-1] 表示插入操作
                    int insert = dp[i][j-1]+ic;
                    // dp[i-1][j] 表示删除操作
                    int delete = dp[i-1][j]+dc;
                    int replace = dp[i-1][j-1]+rc;
                    
                    dp[i][j] = Math.min(Math.min(insert,delete),replace);
                }
            }
        }
        return dp[m][n];
    }
}

赏

谢谢你请我吃糖果

微信