Created
February 4, 2018 02:19
-
-
Save jianminchen/77761d0a92287d01770a1a739e16c7b2 to your computer and use it in GitHub Desktop.
Deletion distance discussion with the peer - dynamic programming
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
) | |
//f[3][4] = f[2][3] | |
//f[4][5] | |
//f[0][0] = 0 | |
//f[i][j] | |
// i == j f[i][j] = f[i-1][j-1] | |
// i !== f[i][j] = min(f[i-1][j],f[i][j-1]) + 1 | |
//f[0][0] = 0 | |
//f[0][1] = 1 | |
//f[0][2] = 2 | |
//... | |
//f[1][1] = min(f[1][0], f[0][1]) + 1 = 2 | |
//... | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment