1
00:00:01,160 --> 00:00:08,810
Before we go ahead and discuss how we can solve this question, let's first take a few moments to discuss.

2
00:00:08,810 --> 00:00:16,250
How can one identify that the edit distance question is actually an LCS type problem?

3
00:00:16,250 --> 00:00:23,570
Now, when we discussed the longest common subsequence problem, we discussed that we would iterate

4
00:00:23,570 --> 00:00:26,990
through the characters of the two strings that are given to us.

5
00:00:26,990 --> 00:00:29,510
And then there were two possibilities.

6
00:00:29,510 --> 00:00:36,770
In one case, we would see that the two characters being compared would be equal, and in another case

7
00:00:36,770 --> 00:00:40,460
we would see that the two characters are not equal.

8
00:00:40,460 --> 00:00:47,150
For example, if the two strings are a, b, c, d, e, and a d e, we would see that these two are

9
00:00:47,150 --> 00:00:53,780
equal, and then we would call the same function that we had written recursively with the subproblem,

10
00:00:53,780 --> 00:00:56,480
which was this over here these two strings.

11
00:00:56,480 --> 00:01:01,520
And then to that answer we would add one to get the LCS.

12
00:01:01,520 --> 00:01:08,570
Now if the two characters were not equal, something like this where you have A over here and B over

13
00:01:08,570 --> 00:01:16,070
here, we discuss that we would have to make two calls and we would only increment one index at a time.

14
00:01:16,070 --> 00:01:20,780
So in one case we would make this as the next subproblem.

15
00:01:20,780 --> 00:01:25,910
And in the other case we would make this as the next subproblem.

16
00:01:25,910 --> 00:01:28,400
So we have already discussed that previously.

17
00:01:28,400 --> 00:01:32,840
Now how is this similar to the edit distance question over here.

18
00:01:33,080 --> 00:01:39,530
Now in the edit distance question also the aim is to convert word one to word two.

19
00:01:39,530 --> 00:01:45,560
And for this we would have to go through the characters of the two strings which are given to us.

20
00:01:45,560 --> 00:01:54,350
And when we compare two characters or characters at two specific indexes in word one and word two respectively,

21
00:01:54,350 --> 00:01:59,180
we would either see that the characters are equal or not equal.

22
00:01:59,180 --> 00:02:02,300
If the characters are equal, then we are good.

23
00:02:02,300 --> 00:02:09,740
No operation is required to make them equal, and we proceed with the remaining parts of word one and

24
00:02:09,740 --> 00:02:10,550
word two.

25
00:02:10,580 --> 00:02:17,750
However, if we compare two characters and they are not equal, we would have three options.

26
00:02:17,750 --> 00:02:23,840
We could either replace a character, delete a character, or insert a character.

27
00:02:23,840 --> 00:02:28,820
Notice how this structure is similar to the LCS problem.

28
00:02:29,000 --> 00:02:37,340
Another hint that can be used to identify the edit distance question as an LCS type question is by observing

29
00:02:37,340 --> 00:02:45,680
the inputs that are given to us, and the expected output in both the LCS question and the edit distance

30
00:02:45,680 --> 00:02:46,520
question.

31
00:02:46,520 --> 00:02:55,370
Notice that we are given two strings as input, and the output which is expected of us is an integer.

32
00:02:55,490 --> 00:03:02,240
In the case of the LCS question, we had to return the length of the longest common subsequence and

33
00:03:02,240 --> 00:03:08,480
over here we have to return the number of operations required to change word one to word two.

34
00:03:08,510 --> 00:03:15,170
This is another hint that can help you think and identify that the edit distance question is in fact

35
00:03:15,170 --> 00:03:17,060
an LCS type question.

36
00:03:17,060 --> 00:03:21,020
In the next video, let's start to solve this question.