Edit Distance

这道题leetcode上面也有，但是leetcode比牛客网这道简单，这道题将插入替换删除的代价进行了分离，这对对这道题里面的插入删除替换三种操作的不同逻辑理解有帮助

class MinCost:
    def findMinCost(self, A, n, B, m, c0, c1, c2):
        # write code here
        dp = [[0] * (n + 1) for _ in xrange(m + 1)]

        for i in xrange(m + 1):
            for j in xrange(n + 1):
                if not i:
                    dp[i][j] = c1 * j
                elif not j:
                    dp[i][j] = c0 * i
                elif A[j - 1] == B[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1] + c2, dp[i - 1][j] + c0, dp[i][j - 1] + c1)

        return dp[m][n]

Java无优化版本

public class MinCost {
    public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        // write code here
        int[][] dp = new int[n + 1][m + 1];
        char[] stringA = A.toCharArray();
        char[] stringB = B.toCharArray();

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) { 
                if (i == 0) {
                    dp[i][j] = j * c0;
                } else if (j == 0) {
                    dp[i][j] = i * c1;
                } else if (stringA[i - 1] == stringB[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + c2, Math.min(dp[i - 1][j] + c1, dp[i][j - 1] + c0));
                }
            }
        }

        return dp[n][m];
    }
}

上面是原始无优化的代码

这道题因为需要更新值也需要老值，所以无法做单排的空间优化而只能优化到两排的

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)

        dp = [[0] * (n + 1) for _ in xrange(2)]

        for i in xrange(m + 1):
            for j in xrange(n + 1):
                if not i:
                    dp[i % 2][j] = j
                elif not j:
                    dp[i % 2][j] = i
                elif word1[j - 1] == word2[i - 1]:
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1]
                else:
                    dp[i % 2][j] = min(dp[(i - 1) % 2][j - 1], dp[(i - 1) % 2][j], dp[i % 2][j - 1]) + 1

        return dp[m % 2][n]