72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[word1.size() + 1][word2.size() + 1];
        for(int i = 0; i <= word1.size(); i++)
            dp[i][0] = i;
        for(int i = 0; i <= word2.size(); i++)
            dp[0][i] = i;
        for(int i = 1; i <= word1.size(); i++)
            for(int j = 1; j <= word2.size(); j++)
                dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i-1][j-1]});
            
        return dp[word1.size()][word2.size()];
    }
};