jayantjpr's blog

Edit Distance using LCS
By jayantjpr, 11 years ago, In English

Hi friends,

I was solving a question on SPOJ (http://www.spoj.com/problems/EDIST) to calculate the Edit Distance between two strings (http://en.wikipedia.org/wiki/Levenshtein_distance).

My Claim is:

Given two strings A & B
 Edit Distance(A,B) = max(|A|,|B|) - |Longest common sub-sequence(A,B)|.
(where |A| means length of string A)

Is there something wrong with the above claim? If yes, could you help me find out a test case on which it fails?

I tried submitting the code (using the above claim), but got a wrong answer. I am already aware of the conventional DP solution as shown on the wikipedia page.

Thanks for you help!

Regards,

Jayant

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it 
ABAC
ADEA
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah! Thanks for the test case!

    I realized my mistake. While claiming above, I was not considering the positions of the letters in the LCS.

    Thanks again! :)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks :)

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, After 10 years, I got my mistake.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I always thought:

|A| + |B| = |SES| + |LCS| * 2

Where SES — shortest edit script and LCS is longest common subsequence.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first time I approached the problem I thought exactly the same as you

→ Reply