题解 | #用两个栈实现队列#

import java.util.*;


public class Solution {
    /**
     * 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整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        if (m == 0 || n == 0) return (m + n) * rc;
        // dp[i][j] 表示 str1 前 i 个字符转换成 str2 前 j 个字符花的最少操作数[即编辑距离]
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i * dc; // str2 长度为0，只能删除
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j * ic; // str1 长度为0， 只能插入
        }
        
        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 {
                    // 以下这些操作都是针对str1 实施的
                    // 例如str1 horse str2 ros
                    // 插入 str1变为 hrorse 此时要将str1 的第一个r前面的字符串 变为
                    // str2 的r 前面的字符串 也就是dp[i][j - 1];
                    int insertNum = ic + dp[i][j - 1];
                    int deleteNum = dc + dp[i - 1][j];
                    int replaceNum = rc + dp[i - 1][j - 1];
                    dp[i][j] = Math.min(insertNum, Math.min(deleteNum, replaceNum));
                }
            }
        }
        return dp[m][n];
    }
}