Skip to content

Instantly share code, notes, and snippets.

@barrysteyn
Created July 14, 2013 21:09
Show Gist options
  • Save barrysteyn/5996061 to your computer and use it in GitHub Desktop.
Save barrysteyn/5996061 to your computer and use it in GitHub Desktop.
/*
* 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()];
}
};
/*
* 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();
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment