Edit Distance(leetcode, cpp,dp)

 ===============================================

 

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

 ===================================================

class Solution {
public:
    int minDistance(string w1, string w2)
    {
        int t[w1.size()+1][w2.size()+1];
        for(int  i=0;i<w2.size()+1;i++)
        {
            t[0][i]=i;
        }
         for(int  i=0;i<w1.size()+1;i++)
        {
            t[i][0]=i;
        }
       
        for(int i=1;i<w1.size()+1;i++)
        {
            for(int j=1;j<w2.size()+1;j++)
            {
                if(w1[i-1]==w2[j-1])
                {
                    t[i][j]=t[i-1][j-1];
                }
                else
                    t[i][j]=min( t[i-1][j-1],     min(t[i-1][j],t[i][j-1]))+1;
            }
        }
        return t[w1.size()][w2.size()];
       
    }
};