Edit distance function

Question

Could you please help me to review my first function (modified from an example) in terms of best practice, coding style suggestions and any obvious language mistake/improvements?

unsigned int edit_distance(const vector<string> &s1, const vector<string> &s2)
{
 const size_t len1 = s1.size(), len2 = s2.size();
 vector<vector<unsigned int>> d(len1 + 1, vector<unsigned int>(len2 + 1));
 d[0][0] = 0;
 for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
 for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;
 for(unsigned int i = 1; i <= len1; ++i)
 for(unsigned int j = 1; j <= len2; ++j)
 {
 unsigned int a = d[i - 1][j] + 1;
 unsigned int b = d[i][j - 1] + 1;
 unsigned int c = d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1);
 d[i][j] = std::min( std::min(a,b), c);
 }
 return d[len1][len2];
}

• AndyClaw: For starters you need a function comment, explain what its doing, use readable variable names. You don't get any performance improvement from minified code.

Answer 1

Do you want unsigned int or do you want std::size_t?

unsigned int edit_distance(const vector<string> &s1, const vector<string> &s2)

It comes down to what you are trying to convey.
The use of string and vector suggests you are doing using namespace std; try not to do this. Prefer to qualify your types: std::string and std::vector.

Personally, I prefer const on the right. But it's only a preference thing.

Only declare one variable per line:

 const size_t len1 = s1.size(), len2 = s2.size();

Come up with better names. d is not very descriptive.

 vector<vector<unsigned int>> d(len1 + 1, vector<unsigned int>(len2 + 1));

I would prefer std::size_t here:

 for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;