题目描述

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

示例1

输入

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

返回值

2

示例2

输入

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

返回值

8

备注:

题目链接：https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4?tpId=188&tqId=38327&rp=1&ru=%2Fta%2Fjob-code-high-week&qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&tab=answerKey

 

class Solution {
public:
    /**
     * 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整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0x3f3f3f3f));
        for(int i=0;i<=str2.size();i++)
        {
            dp[0][i]=i*ic;//0个字符到i字符，需要插入
        }
        for(int i=0;i<=str1.size();i++)
        {
            dp[i][0]=i*dc;//i个字符到0字符，需要删除
        }
        for(int i=0;i<str1.size();i++)
        {
            for(int j=0;j<str2.size();j++)
            {
                if(str1[i]==str2[j])
                {
                    dp[i+1][j+1]=dp[i][j];
                }
                else
                {
                    int insertCost=dp[i+1][j]+ic;
                    int delCost=dp[i][j+1]+dc;
                    int repCost=dp[i][j]+rc;
                    dp[i+1][j+1]=min(insertCost,min(delCost,repCost));
                }
            }
        }
        return dp[str1.size()][str2.size()];
    }
};