// Source : https://oj.leetcode.com/problems/edit-distance/
// Author : Hao Chen
// Date : 2014-08-22
/**********************************************************************************
*
* Given two words word1 and word2, find the minimum number of steps required to
* convert word1 to word2. (each operation is counted as 1 step.)
*
* You have the following 3 operations permitted on a word:
*
* a) Insert a character
* b) Delete a character
* c) Replace a character
*
*
**********************************************************************************/
#include
#include
#include
#include
using namespace std;
int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
if (n1==0) return n2;
if (n2==0) return n1;
vector< vector > m(n1+1);
for(int i=0; i r(n2+1);
r[0] = i;
m[i] = r;
}
for (int i=0; i2){
word1 = argv[1];
word2 = argv[2];
}
int steps = minDistance(word1, word2);
cout << word1 << ", " << word2 << " : " << steps << endl;
return 0;
}