Java-LeetCode72. 编辑距离-动态规划

原题插入删除替换代价都是1

• 算法
  • 1.动态规划：dp[i][j]表示word1的前i个字符编辑成word2的前j个字符需要的最小操作数
  • 2.初始状态：dp[i][0] = i，i次删除；dp[0][i] = i，i次插入
  • 3.过渡公式：
    • 当i字符等于j字符时：dp[i][j] = dp[i-1][j-1]，不需要额外操作
    • 当i字符不等于j字符时：dp[i][j] = Math.min(insert, delete, replace)
    • int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j
    • int delete = dp[i-1][j] + 1; i-1个编辑成j个字母，再删除一个i
    • int replace = dp[i-1][j-1] + 1; i-1个编辑成j-1个字母，再将i替换成j

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 1; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                int insert = dp[i][j-1] + 1;
                int delete = dp[i-1][j] + 1;
                int replace = dp[i-1][j-1] + 1;
                dp[i][j] = Math.min(insert, Math.min(delete, replace));
            }
        }
    }
    return dp[m][n];
}

• 算法
  • 1.优化空间复杂度
  • 2.用一个变量prev保存dp[i]更新前的值，然后用这个变量更新dp[i]

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[] dp = new int[n+1];
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[j] = prev;
            } else {
                int insert = prev + 1;
                int delete = dp[j] + 1;
                int replace = dp[j-1] + 1;
                dp[j] = Math.min(insert, Math.min(delete, replace));
            }
            prev = temp;
        }
    }
    return dp[n];
}

此题插入删除替换代价给定

    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        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++) {
            char c1 = str1.charAt(i-1);
            for(int j = 1; j <= n; j++) {
                char c2 = str2.charAt(j-1);
                if(c1 == c2) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    int insert = dp[i][j-1] + ic;
                    int delete = dp[i-1][j] + dc;
                    int replace = dp[i-1][j-1] + rc;
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        return dp[m][n];
    }