Grokking Algorithms

Chapter 9
 
 
I
 
 
Dynamic programming
The solution
Here’s the final grid.
Here’s my formula for filling in each cell.
Here’s how the formula looks in pseudocode:
if word_a[i] == word_b[j]:
The letters match.
cell[i][j] = cell[i-1][j-1] + 1
else: 
The letters don’t match.
cell[i][j] = 0 

---

183
Longest common substring
Here’s the grid for 
hish vs. vista.
One thing to note: for this problem, the final solution may not be in 
the last cell! For the knapsack problem, this last cell always had the 
final solution. But for the longest common substring, the solution is the 
largest number in the grid—and it may not be the last cell.
Let’s go back to the original question: which string has more in 
common with 
hish? hish
and 
fish
have a substring of three letters in 
common. 
hish
and 
vista
have a substring of two letters in common. 
Alex probably meant to type 
fish
.
Longest common subsequence
Suppose Alex accidentally searched for 
fosh
. Which word did he mean: 
fish
or
 fort
? 
Let’s compare them using the longest-common-substring formula.

---

184
Chapter 9
 
 
I
 
 
Dynamic programming
They’re both the same: two letters! But
 fosh
is closer to 
fish
.
You’re comparing the longest common 
substring
, but you really need 
to compare the longest common 
subsequence
: the number of letters in 
a sequence that the two words have in common. How do you calculate 
the longest common subsequence? 
Here’s the partial grid for 
fish
and
 fosh
.
Can you figure out the formula for this grid? The longest common 
subsequence is very similar to the longest common substring, and 
the formulas are pretty similar, too. Try to solve it yourself—I give the 
answer next.