LeetCode: Edit distance - http://leetcode.com/onlinejudge#question_72

edit_distance_1.cpp

/*
 * 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()];
    }
};

edit_distance_2.cpp

/*
 * 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) {
        vector<vector<int> >dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        
        for (int i=0; i <= word1.size(); i++) {
            for (int j=0; j <= word2.size(); j++) {
                //Base case: dp[0][0] = 0
                //         : dp[i][0] = i
                //         : dp[0][j] = j
                if (!i || !j) {
                    if (!i) dp[i][j] = j;
                    else dp[i][j] = i;
                    continue;
                }
                
                dp[i][j] = min(
                    //1) Characters are equal => dp[i][j] = dp[i-1][j-1]
                    //2) Characters not equal => dp[i][j] = dp[i-1][j-1] +1 (character replace)
                    dp[i-1][j-1] + (word1[i-1] != word2[j-1]),
                    
                    //dp[i-1][j]+1 => delete one character from i-1,
                    // or insert one character from j
                    min(dp[i-1][j]+1, dp[i][j-1]+1)
                );
            }
        }
        
        return dp.back().back();
    }
};