if we can {add,chance,erase} one letter of the word the solution it´s
fine....
but if only can add
DP[i][j]= 0 if i==j
0 if(i+1)==j && word[i]==word[j]
1 if(i+1)==j && word[i]!=word[j]
min(DP[i+1][j],DP[i][j-1]) otherwise
....i think that this it´s fine....
2011/9/7 Dumanshu <[email protected]>
> @Victor:
>
> Instead of 0 and 1, shouldn't it be like DP[i-1][j-1] + 0 and DP[i-1]
> [j-1] + 1????
>
>
> On Sep 7, 1:10 am, Victor Manuel Grijalva Altamirano
> <[email protected]> wrote:
> > Try with DP, a little modicated of Edit Distance algorithm
> >
> > State i=the begin of the word , j=the end of the word
> >
> > DP[i][j]= 0 if i==j
> > 0 if(i+1)==j && word[i]==word[j]
> > 1 if(i+1)==j && word[i]!=word[j]
> > min(DP[i+1][j]+1,DP[i][j-1]+1) otherwise
> > If you have any question ask!!!
> > Good luck!!!
> >
> > Victor Manuel Grijalva Altamirano
> > Universidad Tecnologica de La Mixteca
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Victor Manuel Grijalva Altamirano
Universidad Tecnologica de La Mixteca
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
