ADVEDIST - Advanced Edit Distance
The edit distance of two strings S and T is the minimum number of edit operations that need to be done to transform S into T . The valid edit operations are:
• Insert a single character at any position.
• Modify an existing character.
• Remove an existing character.
For example, the edit distance of “pantera” and “aorta” is 5, because the following chain of
edits is valid (and there is no shorter chain):
“pantera” >>> “antera” >>> “aotera” >>> “aoera” >>> “aora” >>> “aorta”.
We define the advanced edit distance in a similar way, but adding the swap of two adjacent characters as an extra valid operation. With this setting, the advanced edit distance of “pantera” and “aorta” is 4:
“pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”.
You need to write a program that calculates the advanced edit distance of two given words.
The input contains several test cases. Each test case is described in a single line that contains
two non-empty words, each of them of at most 1000 lowercase letters, separated by a single
space. The last line of the input contains two asterisks separated by a single space and should
not be processed as a test case.
For each test case output a single line with an integer representing the advanced edit distance
of the two input words.
great problem!!! O(n^3) gets AC in 0.5s! the test cases must be weak.
What I do not get is while I got AC, I solved using O(n^3) algorithm and given the input size, this complexity seems unacceptable. What is going on here? Have the time constraints been relaxed? Are the test cases not really worst case? Are there any average time analyses indicating that the O(n^3) algorithm is not too bad in practice?Last edit: 2017-01-21 15:08:50
standard probLast edit: 2016-08-26 16:23:05
https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance read this first or try with recursion
free mind ;):
straight implementation of Damerau–Levenshtein distance algorithm :)
can ny1 provide the test case which will give different answers for Optimal string alignment distance and Distance with adjacent transpositions
Clearly written that you are to transform S into T. :/
Piyush Raman Srivastava:
learnt something new.. The 2 versions of Damerau–Levenshtein Algorithm :)
@Somesh Maurya Thanks for the hint :)
it is simple Damerau–Levenshtein distance algorithm..but then y it's not getting accepted :C