SPEAKER 1: Let's take a look at similarities.
In this problem, your job is going to be to take two strings
and to figure out how similar those two strings are to each other.
And we'll define similarity in terms of edit distance.
In particular, edit distance means how many steps or operations
it would take to convert one string into the other string.
If you can convert one string into the other one in very few steps
or operations, then the two strings are probably pretty similar.
But if it takes a lot of steps or operations
to convert one string into the other, than those two strings
are probably pretty different.
Here's what you'll have to do.
First, you'll implement a function called
distances which will return a 2D list or a matrix,
where matrix in row i and column j is going to be a tuple.
Just an encapsulation of multiple values where the first value in the tuple
is the edit distance between the first i characters
of your first string which we'll call a, the first j
characters of your second string which we'll call b.
And so that edit distance is just going to be a number representing
the number of steps it would take to convert from the first i
characters of a into the first j characters of b.
Then the second element in the tuple is going
to be the last operation that you had to take
in the optimal sequence of operations to get from one string to the other.
That operation might be an insert or a deletion or a substitution,
but more on that in a moment.
Then you'll implement an HTML, a file called
index.html which will display a form where
the user can input two strings in order to submit them to be compared,
based on the edit distance algorithm.
And then finally, you'll implement a file called matrix.html
which will display an HTML table representing
all of the possible costs that are returned by distances.
Giving you all of the different costs for converting the first i
characters of string a into the first j characters of string
b for all possible i and j values.
Let's get started.