class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        int n1=word1.length()+1;
        int n2=word2.length()+1;
        
        int min[n1][n2];
        for(int i=0;i<n1;i++) min[i][0]=i;
        for(int i=0;i<n2;i++) min[0][i]=i;
        
        for(int i=1;i<n1;i++)
            for(int j=1;j<n2;j++)
            {
                //replace
                int min1=min[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1);
                //add or delete
                int min2=min[i][j-1]+1;
                int min3=min[i-1][j]+1;
                if(min1>min2) min1=min2;
                if(min1>min3) min1=min3;
                min[i][j]=min1;
            }
        return min[n1-1][n2-1];
    }
};