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

#include <vector>
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) {
        int n1 = str1.length();
        int n2 = str2.length();
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 0; i <= n1; ++i) {
            dp[i][0] = i * dc;
        }
        for (int j = 0; j <= n2; ++j) {
            dp[0][j] = j * ic;
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min({dp[i - 1][j] + dc, dp[i][j - 1] + ic, dp[i - 1][j - 1] + rc});
                }
            }
        }
        return dp[n1][n2];
    }
};

思路：动态规划。

大体思路跟编辑距离1相同。

需要注意的是：str1[i - 1] == str2[j - 1]时，dp[i - 1][j]表示的是，使str1[0...i - 2]位置的字符串与str2[0...i-1]位置的字符串相同所需的最小编辑距离，在此基础上要使str1[0...i - 1]位置的字符串与str2[0...i-1]位置的字符串相同，就必须将str1[i - 1]删去，所以是加上dc而不是ic。