72. Edit Distance

Let dp[i][j] be the minimum edit distance at position i in word1 and position j in word2. We have following two cases to achieve the state transition formula.

Case 1: word1[i] == word2[j]
We don't have to do anything for dp[i][j], so dp[i][j] = dp[i-1][j-1].

Case 2: word1[i] != word2[j]
Suppose we focus on word1, then
(1) Replace word2[j] with word1[i]: dp[i-1][j-1]+1;
(2) Delete word1[i]: dp[i-1][j]+1;
(3) Insert word2[j]: dp[i][j-1]+1;
So we just need to choose the minimum distance from the three cases above.

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