1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int f[510][510];

    int minDistance(string word1, string word2) {
        // 初始化
        int n1 = word1.size(), n2 = word2.size();
        for (int i = 0; i <= n1; i ++) {
            f[i][0] = i;
        }
        for (int i = 0; i <= n2; i ++) {
            f[0][i] = i;
        }

        for (int i = 1; i <= n1; i ++) {
            for (int j = 1; j <= n2; j ++) {
                f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i - 1][j -1] + (word1[i - 1] != word2[j - 1]));
            }
        }

        return f[n1][n2];
    }
};