Leetcode 72: Edit Distance

leetcode_72.cpp

#include <iostream>
#include <vector>

using namespace std;

int minDistance(string word1, string word2) {
    int len1 = word1.size();
    int len2 = word2.size();

    //dp grid will be word1 spanning rows and word2 spans columns.
    vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));

    for (int i=0; i<=len2; ++i) 
        dp[0][i] = i;  //set first row of grid to be 0->len2
    for (int i=0; i<=len1; ++i)
        dp[i][0] = i;  //set first column of grid to be 0->len1

    for (int r=1; r<=len1; ++r) {
        for (int c=1; c<=len2; ++c) {
            int minval = min(dp[r][c-1], min(dp[r-1][c-1], dp[r-1][c]));
            int val = (word1[r-1] == word2[c-1]) ? dp[r-1][c-1] : minval + 1;
            dp[r][c] = val;
        }
    }

    return dp[len1][len2];
}

int main() {
    cout << minDistance("zoologicoarchaeologist", "zoogeologist") << "\n";
    return 0;
}