Mukit09's blog

Printing path in Edit Distance
By Mukit09, 11 years ago, In English

I am new in DP... Now trying to learn edit distance algorithm recursively... But I can't print the path... How can I do this ???

I have been trying since last two days but can't get it... :(

Would anyone please check the code given in the link below and tell me where should I edit to print the path correctly ???

code link

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In order to print the path you need to backtrack.

For example, suppose you are storing results of your subproblems in DP[i][j], what can done is to also store the decision that you made at that step in a separate matrix call it B[i][j].

In this case, DP[i][j]=min{DP[i-1][j]+1,DP[i][j-1]+1,DP[i-1][j-1] if s[i]=t[j], else DP[i-1][j-1]+1}

you can store in BP[i][j] the choice which gave you the min. For example if DP[i][j-1]+1, gave you the min. store (i,j-1) in BP[i][j] as a pair. So you know that at (i,j) you had chosen to delete a character and that before taking that decision you were at BP[i][j-1].

Now in order to print the path start with BP[m][n] and then backtrack using information you had stored in table BP[i][j].

→ Reply