Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

 
//
//   D[i][j] = | D[i-1][j-1])  A[i] == A[j]
//             |
//             | 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])   A[i] != A[j]
//
class Solution {
public:
    int minDistance(string A, string B) {
       
        int m = A.size();
        int n = B.size();
        vector<int> D(n + 1, 0);
       
        for(int j = 0; j <=n; j++)
           D[j] = j;
       
        for(int i = 1; i <= m; i++) {
          int D_i_1_j_1 = i-1; // D[i-1][0]
          D[0] = i;  // D[i][0]
         
          for(int j = 1; j <= n; j++) {
              int T = A[i-1] == B[j-1] ? D_i_1_j_1 : 1 + min(D[j-1], min(D[j], D_i_1_j_1));
              D_i_1_j_1 = D[j];
              D[j] = T;
          }
        }
        return D[n];
    } 
};

// DP2
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        if(m == 0) return n;
        if(n==0) return m;
       
        vector<vector<int>> map(m+1);
        for(int i = 0;i  < m+1; i++)
           map[i] = vector<int>(n+1, 0);
        for(int i = 0; i <=m; i++)
   map[i][0] =i;
  for(int i = 0; i <=n; i++)
   map[0][i] =i;
        for (int i = 1; i <=m; i++)
         for (int j = 1; j <=n; j++)   
          {
              if (word1[i-1] == word2[j-1])
                 map[i][j] = map[i-1][j-1];
              else {
                 map[i][j] = min(map[i-1][j], map[i][j-1]);
                 map[i][j] = min(map[i][j], map[i-1][j-1]);
                 map[i][j] +=1;
              }
          }
            
        return map[m][n];
   
    }
};

// DP 3

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.size();
        int l2 = word2.size();
        vector<int> f(l2+1, 0);
        for (int j = 1; j <= l2; ++j)
            f[j] = j;
        for (int i = 1; i <= l1; ++i)
        {
            int prev = i;
            for (int j = 1; j <= l2; ++j)
            {
                int cur;
                if (word1[i-1] == word2[j-1]) {
                    cur = f[j-1];
                } else {
                    cur = min(min(f[j-1], prev), f[j]) + 1;
                }
                f[j-1] = prev;
                prev = cur;
            }
            f[l2] = prev;
        }
        return f[l2];
    } 
};