OJ Board

cannot reconstruct solution? How do you calculate the minimum distance?

It is needed two-dimensional integer array, say S. After computation, S[m][n] is minimum distance, where m is length of s1 (first string) and n length of s2 (second string). Here is how I do computation:

val = (s1 == s2[j]) ? 0 : 1;
S[j] = min( S[i-1][j-1] + val, S[i-1][j]+1 , S[j-1]+1 );

Levenstein Distance, you understand how and why it works?

Yes, I do. I'm not total newbie to DP as I seem to be.

Still puzzled about outputting...

Maxim

ok then,
let f as source str, t as target string,

to back track:
start from s[m][n], m= len(to), n=len(from)
if(s[m][n]==0) then done
else
compare and found where s[m][n] is from:

again set val = (s[m]==s[n]?0:1)
now, if(s[m][n]==s[m-1][n]+1),
this means you can transform from
f(0..n) to t(0..m-1) using s[m-1][n] operations, so you can do that and than insert t[m] to t(0..m-1). of course you can also first insert t[m] to f(0..n) then transform from f(0..n) to t(0..m-1), and t[m] will append at the end anyways. Set m:=m-1 after operation

similarly, if(s[m][n]==s[m][n-1]+1) refers to a delete at f[n] rather than insert at t in the previous case.

and s[m][n]==s[m-1][n-1]+val refers to a change f val = 1 and no operation when val = 0

But, as I said somehow strangely the judge only accept back track in certain order, whiuch I haven't figure why yet.

Can anyone help me on the output part?

We've to output the position of "changed characters", but as the position of characters will be changed whenever Insert/Delete function is called, what shall we do?

you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM

Dominik Michniewski wrote:you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM

Could you explain a bit further plz?? Why DELETE == do nothing?


P.S. I've no trouble finding the "edit distance"...

There is a similar problem in the volumes but i can't remember.
plz help

When you delete character from input string, position which you must output doesn't change.

Anupam: yes, in volumes exists other problem in this manner - 52x or something like this ...

Best regards
DM

I don't understand...

I got ACC for problem 526, but not this one!!!! Why? Aren't them identical???? Plz help!!!

Finally got ACC. As yiuyuho has mentioned before, the judge only accept back track in certain order.

I used D-C-I and got WA.
Changed to C-D-I and got ACC!!!! Strange...

I think it has got to do with the limit of the strings being 20... if you track in certain order, some of them would give numbers which are beyond 20... like if you track for insert first, then you delete... then you might insert letters beyond the limit of 20 and then delete whatever you want to delete... which is probably what is causing all the WA...