Question->SPOJ.com - Problem EDIST used dynamic programming to solve the
standard
edit distance problem.I have checked all the corner cases.But i m
getting wrong answer on spoj.
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;
}