/*
 * Dynamic programming at its best! The trick is
 * that erasing a character, and inserting a character
 * are inverse operations and therefore can be considered
 * just one operation (See comments below)
 */


class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[word2.size()+1][word1.size()+1];
        
        for (int i=0; i <=word2.size(); i++) {
            for (int j=0; j <= word1.size(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                        //Both characters are equal
                    if (word1[j-1] == word2[i-1]) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        dp[i][j] = min(
                            min(1+dp[i-1][j-1],//Simulates replacing a letter
                                1+dp[i-1][j]), //Simulates deleting a letter from word2 (or inserting a letter from word1)
                            1+dp[i][j-1] //Simulates deleting a letter from word1 or inserting a letter from word 2
                        );
                    }
                }
            }
        }
        
        return dp[word2.size()][word1.size()];
    }
};