Edit distance between two strings

 #include <iostream>

#include <climits>

#include <cstring>

using namespace std;

int min(int a, int b, int c)

{

    return (a<b)? (a<c?a:c):(b<c?b:c);

}

int editDistance(char* s, char* t, int i, int j)

{  

    if(i==0)

        return j;

    if(j==0)

        return i;

        

        

    if(s[i]!=t[j])

    {

        //either s[0, i-1] = t[j] or s[0, i-1] = t[0, j-1] or s[0, i] = t[0,j-1]

        return 1+min(editDistance(s,t,i-1,j), editDistance(s,t,i-1,j-1), editDistance(s,t,i,j-1));

    }

    else

        return editDistance(s, t, i-1, j-1); //it is same as the ed(s[0,i-1], t[0,j-1]

}

int main() {

// your code goes here

char s[] = "organisation";

char t[] = "organisaton";

int dist = editDistance(s, t, strlen(s)-1, strlen(t)-1);

cout << "edit distance of " << s << " and " << t << " is " << dist;

return 0;

}

Output:

edit distance of organisation and organisaton is 1

---------------------------------------------------------------------------------------------

#include <iostream>

#include <climits>

#include <cstring>

using namespace std;

int min(int a, int b, int c)

{

    return (a<b)? (a<c?a:c):(b<c?b:c);

}

int editDistance(char* s, char* t, int i, int j, int mem[100][100])

{

    if(i <0 || j<0)

        return 1;

    

    if(mem[i][j] != -1)

        return mem[i][j];

        

    if(i==0)

        return j;

    if(j==0)

        return i;

        

        

    if(s[i]!=t[j])

    {

        //either s[0, i-1] = t[j] or s[0, i-1] = t[0, j-1] or s[0, i] = t[0,j-1]

        mem[i][j] = 1+min(editDistance(s,t,i-1,j, mem), editDistance(s,t,i-1,j-1, mem), editDistance(s,t,i,j-1, mem)); 

    }

    else

        mem[i][j] = editDistance(s, t, i-1, j-1, mem); //it is same as the ed(s[0,i-1], t[0,j-1]

        

    return mem[i][j];

}

int main() {

// your code goes here

char s[] = "thsi is a bir senrence to find eit distance";

char t[] = "this is a big sentence to find edit distance";

int mem[100][100];

memset(mem, -1, sizeof(mem));

int dist = editDistance(s, t, strlen(s)-1, strlen(t)-1, mem);

cout << "edit distance of <" << s << "> and <" << t << "> is " << dist;

return 0;

}

Output:

edit distance of <thsi is a bir senrence to find eit distance> and <this is a big sentence to find edit distance> is 5

----------------------------------------------

3.5ms 5.5KB memory  (with memorisation)

5s 5.4KB memory (without memorisation)