1. class Solution {
    2.     public int minDistance(String word1, String word2) {
    3.         int n = word1.length();
    4.         int m = word2.length();
    6.         // 有一个字符串为空串
    7.         if (n * m == 0) {
    8.             return n + m;
    9.         }
    11.         // DP 数组
    12.         int[][] D = new int[n + 1][m + 1];
    14.         // 边界状态初始化
    15.         for (int i = 0; i < n + 1; i++) {
    16.             D[i][0] = i;
    17.         }
    18.         for (int j = 0; j < m + 1; j++) {
    19.             D[0][j] = j;
    20.         }
    22.         // 计算所有 DP 值
    23.         for (int i = 1; i < n + 1; i++) {
    24.             for (int j = 1; j < m + 1; j++) {
    25.                 int left = D[i - 1][j] + 1;
    26.                 int down = D[i][j - 1] + 1;
    27.                 int left_down = D[i - 1][j - 1];
    28.                 if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
    29.                     left_down += 1;
    30.                 }
    31.                 D[i][j] = Math.min(left, Math.min(down, left_down));
    32.             }
    33.         }
    34.         return D[n][m];
    35.     }
    36. }
    1. class Solution:
    2.     def minDistance(self, word1: str, word2: str) -> int:
    3.         m, n = len(word1), len(word2)
    4.         dp = [[-1] * (n + 1) for _ in range(m + 1)]
    6.         def dp_dist(i, j):
    7.             if dp[i][j] >= 0:
    8.                 return dp[i][j]
    9.             if i * j == 0:
    10.                 dp[i][j] = i + j          
    11.             elif word1[i - 1] == word2[j - 1]:
    12.                 dp[i][j] = dp_dist(i - 1, j - 1)
    13.             else:
    14.                 dp[i][j] = 1 + min(dp_dist(i - 1, j), dp_dist(i, j - 1), dp_dist(i - 1, j - 1))
    15.             return dp[i][j]
    17.         return dp_dist(m, n)
    1. class Solution {
    2. public:
    3.     int minDistance(string word1, string word2) {
    4.         int n = word1.size(), m = word2.size();
    5.         word1 = ' ' + word1;  //添加空格
    6.         word2 = ' ' + word2;
    7.         vector<vector<int>>f(n + 1, vector<int>(m + 1));
    8.         for(int i = 0; i <= n; i++)  f[i][0] = i;  //i次删除
    9.         for(int i = 0; i <= m; i++)  f[0][i] = i;  //i次删除 word1 -> word2
    10.         for(int i = 1; i <= n; i++)
    11.             for(int j = 1; j <= m; j++){
    12.                 f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;      //添加或者删除
    13.                 if(word1[i] == word2[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
    14.                 else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); //替换
    15.             }
    16.         return f[n][m];    
    17.     }
    18. };