[Solved]: Edit distance between two strings

Problem Detail: 

If X denotes the length of string s1 and Y denotes the length of the string s2, then the edit distance between s1 and s2 is never more than
Min(X,Y) or Max(X,Y)?
Please explain.

Asked By : Anshu Mishra

Answered By : Ran G.

It depends on the exact definition of edit distance:

Let, $s1=a$, $s2=bb$

The edit distance between $s1,s2$ is 3 if allowed only insertions and deletions; but it is 2 if allowed insertions, deletions and substitutions.

With substitutions, it is clear that the number of letters you need to change is at most the length of the longer string.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45674

3.2K people like this

 Download Related Notes/Documents