View difference between Paste ID: e90xDEK5 and

-
+#include <algorithm>
 #include <iostream>
 #include <string>
 #include <vector>
 using namespace std;
 
 int levenshtein_distance(const string& s1, const string& s2) {
   int len1 = s1.size();
   int len2 = s2.size();
   // Put the shorter string first to save memory.
   if(len2 < len1)
     return levenshtein_distance(s2, s1);
   int row, col;
   // costs[i] will be the cost of editing s1.substr(0, i) to s2.substr(0, row)
   vector<int> costs(len1 + 1);
   for(col = 0; col <= len1; ++col)
     // Cost of editing s1.substr(0, col) to "" is col * deletions.
     costs[col] = col;
   // previous_costs[i] will be the cost of
   // editing s1.substr(0, i) to s2.substr(0, row-1)
   vector<int> previous_costs(len1 + 1);
   for(row = 1; row <= len2; ++row) {
     previous_costs.swap(costs);  // fast alternative to previous_costs = costs
     // Cost of editing "" to s2.subst(0, row) is row * insertions.
     costs[0] = row;
     for(col = 1; col <= len1; ++col)
       costs[col] = min(min(
           costs[col-1] + 1,  // Cost of removing the letter s1[col-1].
           previous_costs[col] + 1),  // Cost of adding the letter s2[row-1].
           previous_costs[col-1] + (   // Cost of replacing
             (s1[col-1] == s2[row-1]) ? 0 : 1));  // s1[col-1] with s2[row-1].
   }
   return costs[len1];
 }