### Блог пользователя jayantjpr

Автор jayantjpr, 5 лет назад, ,

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

 » 5 лет назад, # |   +11 ABAC ADEA 
•  » » 5 лет назад, # ^ |   0 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! :)
•  » » 14 месяцев назад, # ^ |   0 Thanks a lot!
•  » » 12 месяцев назад, # ^ |   0 Thanks :)
 » 5 лет назад, # |   0 I always thought: |A| + |B| = |SES| + |LCS| * 2Where SES — shortest edit script and LCS is longest common subsequence.