72 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) {
        vector<int> level = vector<int>(word2.size()+1,0);
        vector<vector<int>> res = vector<vector<int>>(word1.size()+1,level);
        for (int j=1;j<=word2.size();j++)
            res[0][j]=j;
        for (int i=1;i<word1.size()+1;i++)
        {
            res[i][0]=i;
            for (int j=1;j<word2.size()+1;j++)
            {
                if (word1[i-1]==word2[j-1])
                {
                    res[i][j]=res[i-1][j-1];
                }
                else
                {
                    res[i][j]=min_val(res[i-1][j],res[i][j-1],res[i-1][j-1])+1;
                }
            }
        }
        return res[word1.size()][word2.size()];
    }
    int min_val(int a,int b,int c)
    {
        int d = a<b?a:b;
        return d<c? d:c;
    }
};