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

// dp[i][j]: min # edit to transform str1[0, i-1] to str2[0, j-1]
// 
// e.g.  str1=abc str2=abd 
//
// if str1[i-1] == str2[j-1]
//   dp[i][j] = dp[i-1][j-1]    啥都不变
// else
//   dp[i][j] = 
//      MIN(dp[i-1][j] + 1,     删除  ab=>abd + 删除c
//          dp[i][j-1] + 1,     插入  abc=>ab + 插入d
//          dp[i-1][j-1]) + 1， 替换  ab=>ab + c=>d 
//   )
// }
//
// O(m*n), O(m*n)

public class Solution {
    public int editDistance (String str1, String str2) {
      int row = str1.length();
      int col = str2.length();
      int[][] dp = new int[row+1][col+1];
      
      // dp[i][0] = i; dp[0][j] = j;
      for (int i = 0; i <= row; i++) dp[i][0] = i;
      for (int j = 0; j <= col; j++) dp[0][j] = j;
      
      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] = 1 + Math.min(
              dp[i-1][j],
              Math.min(dp[i][j-1], dp[i-1][j-1]));
          }
        }
      }
      
      return dp[row][col];
    }
}