[LeetCode] 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.length();
        int len2 = word2.length();
        int dp[len1+1][len2+1];
        for(int i=0;i<=len1;i++)
        {
            dp[i][0] = i;
        }
        for(int i=1;i<=len2;i++)
        {
            dp[0][i] = i;
        }
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(word1[i-1] == word2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    int c = min(dp[i-1][j] + 1, dp[i][j-1]+1);
                    dp[i][j] = min(c, dp[i-1][j-1]+1);
                }
            }
        }
        return dp[len1][len2];
    }
};