题解 | JAVA DP #编辑距离(二)# [P1-T2]

跟(一)一样的。 搞清楚插入/删除分别对应的是dp[][]里的哪个位置就行

// dp[i][j]: min # edit to transform str1[0, i] to str2[0, j]
// NOTE：因为dp[0][j]对应空字符串str1，dp[i][0]对应空字符串str2,
//       所以其实dp[i][j]对应的是str1[0, i-1] to str2[0, j-1]
//
// 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,    str1[0:i-1]变str2[0:j] + 删除str1[i]
//          dp[i][j-1] + ic,    str1[0:i]变str2[0:j-1] + 插入str2[j]
//          dp[i-1][j-1]) + rc， str1[0:i-1]变str2[0:j-1] + 替换str1[i]=>str2[j]
//   )
// }
//
// O(m*n), O(m*n)

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) {
      int row = str1.length();
      int col = str2.length();
      int[][] dp = new int[row+1][col+1];
     
      // 初始dp的第一行和第一列
      for (int i = 0; i <= row; i++) dp[i][0] = i * dc; // str2='' 只能删除
      for (int j = 0; j <= col; j++) dp[0][j] = j * ic; // str1='' 只能插入
       
      for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
          if (str1.charAt(i-1) == str2.charAt(j-1)) {
            dp[i][j] = dp[i-1][j-1];
          } else {
            dp[i][j] = Math.min(
              dp[i-1][j] + dc, Math.min(
              dp[i][j-1] + ic, 
              dp[i-1][j-1] + rc));
          }
        }
      }
       
      return dp[row][col];
    }
}