Edit Distance Solutions in C++

// Source : https://oj.leetcode.com/problems/edit-distance/
// Author : Hao Chen
// Date   : 2014-08-22



#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


/*
 *  Dynamic Programming
 *
 *    Definitaion
 *
 *        m[i][j] is minimal distance from word1[0..i] to word2[0..j]
 *
 *    So, 
 *
 *        1) if word1[i] == word2[j], then m[i][j] == m[i-1][j-1].
 *
 *        2) if word1[i] != word2[j], then we need to find which one below is minimal:
 *
 *             min( m[i-1][j-1], m[i-1][j],  m[i][j-1] )
 *            
 *             and +1 - current char need be changed.
 *
 *        Let's take a look  m[1][2] :  "a" => "ab" 
 *
 *               +---+  +---+                                         
 *        ''=> a | 1 |  | 2 | '' => ab                                
 *               +---+  +---+                                         
 *                                                                    
 *               +---+  +---+                                         
 *        a => a | 0 |  | 1 | a => ab                                 
 *               +---+  +---+                                         
 *                                                            
 *        To know the minimal distance `a => ab`, we can get it from one of the following cases:
 *
 *            1) delete the last char in word1,  minDistance( '' => ab ) + 1                                                             
 *            2) delete the last char in word2,  minDistance(  a => a ) + 1                                                             
 *            3) change the last char,           minDistance( '' => a ) + 1                                                             
 *                                                            
 *  
 *    For Example:
 *
 *        word1="abb", word2="abccb"
 *
 *        1) Initialize the DP matrix as below:
 *
 *               "" a b c c b
 *            "" 0  1 2 3 4 5
 *            a  1
 *            b  2
 *            b  3
 *
 *        2) Dynamic Programming
 *
 *               "" a b c c b
 *            ""  0 1 2 3 4 5
 *            a   1 0 1 2 3 4 
 *            b   2 1 0 1 2 3
 *            b   3 2 1 1 2 2
 *
 */
int min(int x, int y, int z) {
    return std::min(x, std::min(y,z));
}

int minDistance(string word1, string word2) {
    int n1 = word1.size();     
    int n2 = word2.size();     
    if (n1==0) return n2;
    if (n2==0) return n1;
    vector< vector<int> > m(n1+1, vector<int>(n2+1));
    for(int i=0; i<m.size(); i++){
        m[i][0] = i;
    }
    for (int i=0; i<m[0].size(); i++) {
        m[0][i]=i;
    }

    //Dynamic Programming
    int row, col;
    for (row=1; row<m.size(); row++) {
        for(col=1; col<m[row].size(); col++){
            if (word1[row-1] == word2[col-1] ){
                m[row][col] = m[row-1][col-1];
            }else{
                int minValue = min(m[row-1][col-1], m[row-1][col],  m[row][col-1]);
                m[row][col] = minValue + 1;
            }
        }
    }

    return m[row-1][col-1];
}


int main(int argc, char**argv)
{
    string word1="abb", word2="abccb";
    if (argc>2){
        word1 = argv[1];
        word2 = argv[2];
    }

    int steps = minDistance(word1, word2);

    cout << word1 << ", " << word2 << " : " << steps << endl;
    return 0;
}

#include <vector>
using std::vector;
#include <string>
using std::string;
#include <algorithm>
using std::min;

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

/// Source : https://leetcode.com/problems/edit-distance/
/// Author : liuyubobobo
/// Time   : 2018-11-23

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Memory Serach
/// Time Complexity: O(len(word1) * len(word2))
/// Space Complexity: O(len(word1) * len(word2))
class Solution {

private:
    map<pair<int, int>, int> dp;

public:
    int minDistance(string word1, string word2) {
        return dfs(word1, word2, 0, 0);
    }

private:
    int dfs(const string& word1, const string& word2, int index1, int index2){

        if(index1 == word1.size())
            return word2.size() - index2;

        if(index2 == word2.size())
            return word1.size() - index1;

        pair<int, int> hash = make_pair(index1, index2);
        if(dp.count(hash))
            return dp[hash];

        int res = INT_MAX;
        if(word1[index1] == word2[index2])
            res = min(res, dfs(word1, word2, index1 + 1, index2 + 1));

        res = min(res, 1 + dfs(word1, word2, index1, index2 + 1));
        res = min(res, 1 + dfs(word1, word2, index1 + 1, index2));
        res = min(res, 1 + dfs(word1, word2, index1 + 1, index2 + 1));
        return dp[hash] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/edit-distance/
/// Author : liuyubobobo
/// Time   : 2018-11-23

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(len(word1) * len(word2))
/// Space Complexity: O(len(word1) * len(word2))
class Solution {

public:
    int minDistance(string word1, string word2) {

        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        for(int i = 0; i <= m; i ++)
            dp[i][0] = i;
        for(int j = 0; j <= n; j ++)
            dp[0][j] = j;

        // get dp[i][j], check word[i - 1], word[j - 1]
        for(int i = 1; i <= m; i ++)
            for(int j = 1; j <= n; j ++){
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j - 1]);
                dp[i][j] = min(dp[i][j], 1 + dp[i - 1][j]);
                dp[i][j] = min(dp[i][j], 1 + dp[i][j - 1]);
            }

        return dp[m][n];
    }
};


int main() {

    return 0;
}