Deletion distance dynamic programming

Feb. 6, 2018

Introduction

I still have difficult time once a while in terms of solving dynamic programming solution. The underneath recursive design of dynamic programming takes more time to practice.  I had a mock interview last weekend and the peer showed me his way to solve the deletion distance.

It is such nice learning experience from the peer. The code is written in Java and the link is here.

Most of important is that the peer showed me how he proved that recurrence formula is correct. Here is the transcript of the analysis.

Follow up 

I asked the peer in mock interview and then we discussed the formula why distance("heat","hit") = distance("hea", "hit").

Here is the discussion:

 //$dog and $frop,
  //$hit, i =   3 $heat, j = 4
  //f[$hit][$heat] = f[$hi][$hea]
  (f[$hit][$hea] + 1)
  (f[$hi][$heat] + 1)
  (f[$hi][$hea]  <- minimum
    min(f[$h][$hea], $f[$hi][$he]) + 1
  )


Let me write down the explanation given by the peer on March 12, 2018. First let me read his explanation and then figure out his reasoning.

First the peer thinks that it is better to add extra char to stand for empty string "", using '$' char.

There are 3 choices to determine the deletion distance between two string "$hit" and "$heat". There are three choices, in other words, here is the expression:

f[$hit][$heat] = Math.Min(f[$hi][$hea], f[$hit][$hea] + 1, f[$hi][$heat] + 1),

We should be able tell that minimum one is f[$hi][$hea].

Follow up 

July 9, 2018

The peer contacted me to ask practice together. I was so surprised since he won ICPC regional contest in 2012. It is the first time I have a peer to practice together with highly competitive skills in contest.

I just quickly looked up his review back in Feb. 3, 2018 6:00 PM. What I did is to check date connected on linkedin, and then found the mock interview round login, and then looked up algorithm. And then I found the blog, and mock interview feedback.