fork(3) download 
  1. #include <string>
  2. #include <map>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6. int counter = 0;
  7.  
  8. int match(char c1, char c2){
  9.   return c1 == c2 ? 0 : 1;
  10. }
  11.  
  12. int edit_distance(string s1, string s2,map<pair<string,string>, int>& memo){
  13.   if(memo[make_pair(s1,s2)])
  14.     return memo[make_pair(s1,s2)];
  15.   int i = s1.size();
  16.   int j = s2.size();
  17.  
  18.   if(s1.empty())
  19.     return memo[make_pair(s1,s2)] = 1 + j;
  20.   if(s2.empty())
  21.     return memo[make_pair(s1,s2)] = 1 + i;
  22.  
  23.   int opt[3];
  24.  
  25.   opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[0],s2[0]);
  26.   opt[1] = edit_distance(s1.substr(1), s2,memo) + 1;
  27.   opt[2] = edit_distance(s1, s2.substr(1),memo) + 1;
  28.  
  29.   int min = opt[0];
  30.   for(int i = 1; i < 3; i++){
  31.     if(opt[i] < min)
  32.       min = opt[i];
  33.   }
  34.   memo[ make_pair(s1,s2) ] = min;
  35.   return min;
  36. }
  37.  
  38. int edit_distance_driver(string s1, string s2){
  39.   map<pair<string,string>,int> memo;
  40.   return edit_distance(s1, s2, memo);
  41. }
  42.  
  43. int main(){
  44.   cout << edit_distance_driver("thou shalt not","you should not") << endl;
  45.   return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin 
Standard input is empty
stdout 
6
https://ideone.com/QKC1IN
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!