Edit Distance

#include<iostream>
#include<string>
#include<vector>

using namespace std;

// Below function returns the minimum edits (insert/delete/replace)
// that are required to convert word1 to word2
int MinimumEdits (string word1, string word2) {

    // Allocate memory to the DP table
    int **table = new int * [word1.size() + 1];

    for (int i=0; i<=word1.size(); i++) {
        table[i] = new int [word2.size() + 1];
    }

    // Set the base case values
    for (int i=0; i<=word1.size(); i++) {
        table[i][0] = i;
    }

    for (int i=0; i<=word2.size(); i++) {
        table[0][i] = i;
    }

    // Calculate the minimum edits
    for (int i=1; i<=word1.size(); i++) {
        for (int j=1; j<=word2.size(); j++) {

            if(word1.at(i-1) == word2.at(j-1)) {
                table[i][j] = table[i-1][j-1];
            } else {
                int min_val = min(table[i-1][j], table[i][j-1]);
                min_val = min(min_val, table[i-1][j-1]) + 1;
                table[i][j] = min_val;
            }
        }
    }

    int min_edits = table[word1.size()][word2.size()];

    // Free the memory
    for (int i=0; i<=word1.size(); i++)
         delete[] table[i];
    delete[] table;

    return min_edits;
}

int main() {

    vector<string> from = { "zebra", "lion", "sun", "two"};
    vector<string> to = { "bra", "leon", "sunny", "twice" };

    for (int i=0; i<from.size(); i++)
         cout << "Minimum edit required to convert " + from[i] + " to " + to[i] + " : " << MinimumEdits (from[i], to[i]) << endl;

    return 0;
}

Minimum edit required to convert zebra to bra : 2
Minimum edit required to convert lion to leon : 1
Minimum edit required to convert sun to sunny : 2
Minimum edit required to convert two to twice : 3