[LeetCode] Edit Distance

 1 class Solution {
 2 public:
 3     int minDistance(const string& word1, const string& word2) {
 4         int n = word1.size();
 5         int m = word2.size();
 6         vector<vector<int>> f(n+1, vector<int>(m+1));
 7         for (int i = 0; i <= n; i++) {
 8             for (int j = 0; j <= m; j++) {
 9                 if (i == 0) {
10                     f[i][j] = j;
11                 } else if (j == 0) {
12                     f[i][j] = i;
13                 } else {
14                     f[i][j] = f[i-1][j-1] + 1 - (word1[i-1] == word2[j-1]);
15                     f[i][j] = min(f[i][j], f[i][j-1] + 1);
16                     f[i][j] = min(f[i][j], f[i-1][j] + 1);
17                 }
18             }
19         }
20         return f[n][m];
21     }
22 };