Before we go ahead and discuss how we can solve this question, let's first take a few moments to discuss.
How can one identify that the edit distance question is actually an LCS type problem?
Now, when we discussed the longest common subsequence problem, we discussed that we would iterate
through the characters of the two strings that are given to us.
And then there were two possibilities.
In one case, we would see that the two characters being compared would be equal, and in another case
we would see that the two characters are not equal.
For example, if the two strings are a, b, c, d, e, and a d e, we would see that these two are
equal, and then we would call the same function that we had written recursively with the subproblem,
which was this over here these two strings.
And then to that answer we would add one to get the LCS.
Now if the two characters were not equal, something like this where you have A over here and B over
here, we discuss that we would have to make two calls and we would only increment one index at a time.
So in one case we would make this as the next subproblem.
And in the other case we would make this as the next subproblem.
So we have already discussed that previously.
Now how is this similar to the edit distance question over here.
Now in the edit distance question also the aim is to convert word one to word two.
And for this we would have to go through the characters of the two strings which are given to us.
And when we compare two characters or characters at two specific indexes in word one and word two respectively,
we would either see that the characters are equal or not equal.
If the characters are equal, then we are good.
No operation is required to make them equal, and we proceed with the remaining parts of word one and
word two.
However, if we compare two characters and they are not equal, we would have three options.
We could either replace a character, delete a character, or insert a character.
Notice how this structure is similar to the LCS problem.
Another hint that can be used to identify the edit distance question as an LCS type question is by observing
the inputs that are given to us, and the expected output in both the LCS question and the edit distance
question.
Notice that we are given two strings as input, and the output which is expected of us is an integer.
In the case of the LCS question, we had to return the length of the longest common subsequence and
over here we have to return the number of operations required to change word one to word two.
This is another hint that can help you think and identify that the edit distance question is in fact
an LCS type question.
In the next video, let's start to solve this question.