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

class Solution {

public:

    int minDistance(string word1, string word2) {

        int len1 = word1.size();

        int len2 = word2.size();

        vector<vector<int>> v (len1+1, vector<int>(len2+1, 0));

        if (len1 == 0) return len2;

        if (len2 == 0) return len1;

        for (int i = 0; i< len1+1; i++) {

            for (int j = 0; j< len2+1; j++) {

                if (i == 0) v[i][j] = j;

                else if (j == 0) v[i][j] = i;

                else if (word1[i-1] == word2[j-1]) v[i][j] = v[i-1][j-1];

                else v[i][j] = 1+ min(min(v[i-1][j], v[i][j-1]), v[i-1][j-1]);

            }

        }

        return v[len1][len2];

    }

};