Jun 25, 2017

edit distance of two strings


#include <iostream>
#include <string.h>
using namespace std;

int min(int x, int y, int z)
{
 return (x<y)?(x<z?x:z):(y<z?y:z);
}
/*

ed(s1[1,m], s2[1,n]) = ed(s1[1,m-1], s2[1,n-1]) if s1[m] == s2[n];
      = 1+ min( ed(s1[1-m-1], s2[1,n]),  remove  s1[m]
      ed(s1[1-m-1], s2[1,n-1])   replace s1[m] with s2[n]  
      ed(s1[1-m], s2[1,n-1]) )   insert s2[n] 
      if s1[m] != s2[n] 

*/
int editDistance(char* s1, int m, char* s2, int n)
{
 if(m==0)
  return n;
 if(n==0)
  return m;
  
 if(s1[m-1] == s2[n-1])
 {
  return editDistance(s1, m-1, s2, n-1);
 }
 return 1+ min(editDistance(s1,m-1, s2,n), \
 editDistance(s1, m-1, s2, n-1), editDistance(s1, m, s2, n-1));
}
int main() {
 // your code goes here
 char s1[] = "banana";
 char s2[] = "bana";
 char s3[] = "apple";
 char s4[] = "banaba";
 char s5[] = "bonanza";
 char s6[] = "banamf";
 
 cout << "edit of " << s1 << "-" << s2 << "=" \
 << editDistance(s1,strlen(s1), s2, strlen(s2)) << endl;
 cout << "edit of " << s1 << "-" << s3 << "=" \
 << editDistance(s1,strlen(s1), s3, strlen(s3)) << endl;
 cout << "edit of " << s1 << "-" << s4 << "=" \
 << editDistance(s1,strlen(s1), s4, strlen(s4)) << endl;
 cout << "edit of " << s1 << "-" << s5 << "=" \
 << editDistance(s1,strlen(s1), s5, strlen(s5)) << endl;
 cout << "edit of " << s1 << "-" << s6 << "=" \
 << editDistance(s1,strlen(s1), s6, strlen(s6)) << endl;
 return 0;
}

edit of banana-bana=2
edit of banana-apple=5
edit of banana-banaba=1
edit of banana-bonanza=2
edit of banana-banamf=2

No comments: