# Edit distance problem (dp)

Question->http://www.spoj.com/problems/EDIST/.I used dynamic programming to solve the
standard
edit distance problem.I have checked all the corner cases.But i m
Can anybody tell the counter case where this code fails.

``````#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int t;unsigned int m,n;
string::iterator i,j;
scanf("%d",&t);getchar();
while(t--)//test cases
{
string *a=new string;
string *b=new string;
getline(cin,*a);m=(*a).length()+1;//cout<<m;
getline(cin,*b);n=(*b).length()+1;//cout<<n;
long int **edit=new long int*[m];
for(unsigned int k=0;k<m;k++){edit[k]=new long int[n];}

for(unsigned int x=0;x<m;x++)
{
for(unsigned int y=0;y<n;y++)
{
if(x==0&&y==0){edit[x][y]=0;}
else if(x==0){edit[x][y]=edit[x][y-1]+1;}//insert operation
else if(y==0){edit[x][y]=edit[x-1][y]+1;}//delete operation
else
{   i=(*a).begin()+x-1;j=(*b).begin()+y-1;
if(*i==*j){ edit[x][y]=edit[x-1][y-1];}
else
{
edit[x][y]=min(min(edit[x-1][y-1]+1,edit[x-1][y]+1),edit[x][y-1]+1);
}
}
}
}

printf("%ld\n",edit[m-1][n-1]);
for(unsigned int k=0;k<m;k++){delete []edit[k];}
delete edit;
delete a;
delete b;
}
return 0;
}``````

#include
#include <stdlib.h>

#include<string.h>
using namespace std;

inline int minn(int a,int b,int c)

{
int m = a;
if (m > b) m = b;
if (m > c) m = c;
return m;
}

int main()
{

char s[2001];
char s2[2001];

``````int** arr;

arr = new int*[ 2001 ];
for( size_t i = 0; i < 2001; ++i )
arr[ i ] = new int[ 2001 ];
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int flag=0;
scanf("%s",&s);
scanf("%s",&s2);
int len1=strlen(s);
int len2=strlen(s2);
//Aprintf("%d %d\n",len1,len2);
//memset(arr,0,sizeof(arr));

//for(int j=0;j<=len1;j++)
//{
//  for(int k=0;k<=len2;k++)
//{
//  arr[j][k]=0;
//}
//}
for(int j=0;j<=len2;j++)
arr[0][j]=j;
for(int j=0;j<=len1;j++)
arr[j][0]=j;
/* for(int j=0;j<=len1;j++)
{
for(int k=0;k<=len2;k++)
{
printf("%d ",arr[j][k]);
}
printf("\n");
}
printf("\n\n");*/
for(int j=1;j<=len1;j++)
{
for(int k=1;k<=len2;k++)
{
if(s[j-1]==s2[k-1])
{
flag=0;
}
else
{
flag=1;
}
//printf("%d ",flag);
arr[j][k]=minn((arr[j][k-1]+1),(arr[j-1][k]+1),(arr[j-1][k-1]+flag));
}
//printf("\n");
}

/*for(int j=0;j<=len1;j++)
{
for(int k=0;k<=len2;k++)
{
printf("%d ",arr[j][k]);
}
printf("\n");
}
``````

*/ printf("%d\n",arr[len1][len2]);
}
return 0;
}

it works and based on same dp algorithm

@ankit aggarwal thanks