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.

  • 1
    $\begingroup$ The worst case is when they have nothing in common. If I gave you the 5-char string "AAAAA", and the 8-char string "BBBBBBBB", what's the edit distance between them? Why? Because this is a "worst case", if you extend that reasoning, you'll have an answer and a proof. $\endgroup$ – Alex Meiburg Aug 29 '15 at 6:04

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.