1
00:00:00,420 --> 00:00:02,610
Hi, everyone, welcome to this new video.

2
00:00:02,730 --> 00:00:06,150
So in this video, we are going to cover one question world.

3
00:00:07,950 --> 00:00:11,090
So in this world later, what is the problem statement?

4
00:00:11,340 --> 00:00:17,840
So you will be given one big word when and N-word and one list of words allowed.

5
00:00:18,090 --> 00:00:26,300
So, for example, if the N-word is heard, so is the big N-word and the N-word is COAG.

6
00:00:26,310 --> 00:00:27,780
And this is the word list.

7
00:00:28,290 --> 00:00:31,470
So word list contains a list of words that are allowed.

8
00:00:31,770 --> 00:00:39,690
So what you need to do, you need to convert this word, convert into the N-word and all the intermediate

9
00:00:39,780 --> 00:00:42,230
word must be present in the word list.

10
00:00:42,750 --> 00:00:47,560
And at one time, in one step, you can only change one character.

11
00:00:48,480 --> 00:00:52,090
So, for example, first of all, I will convert hate into.

12
00:00:52,140 --> 00:00:54,240
So let me see, what is this step?

13
00:00:54,270 --> 00:00:59,780
So the steps are I will convert the word hurting to first of all, heart.

14
00:01:00,840 --> 00:01:02,460
So I am changing ivied.

15
00:01:02,530 --> 00:01:06,210
Oh, and this word heart must represent the wordlist.

16
00:01:06,630 --> 00:01:08,700
So in the wordlist heart this present.

17
00:01:09,030 --> 00:01:14,860
So I am converting heart into d'arte so let's convert heart into dard.

18
00:01:15,210 --> 00:01:18,930
So I'm converting Ajin to be at one time.

19
00:01:18,930 --> 00:01:24,330
In one step I can change only one character that is also present then dog.

20
00:01:24,750 --> 00:01:31,330
So convert the G and dog is also present.

21
00:01:31,650 --> 00:01:41,130
So after this what I'm going to do, I'm going to convert this DBI C so it will become COAG and COAG

22
00:01:41,130 --> 00:01:43,410
is also present in the WORDLIST.

23
00:01:43,540 --> 00:01:44,030
Right.

24
00:01:44,280 --> 00:01:51,250
So our output will be how many words are present in this transformation sequence.

25
00:01:51,510 --> 00:01:58,110
So in total five words are present, including the first word and also including the last word.

26
00:01:58,140 --> 00:02:00,900
So in total, five words are there.

27
00:02:01,050 --> 00:02:01,530
Right?

28
00:02:01,620 --> 00:02:07,300
So we need to return the number of words that are in short text transformation sequence.

29
00:02:07,560 --> 00:02:13,680
So in total, five words are there and we need to include being involved in the calculation and also

30
00:02:13,680 --> 00:02:15,310
the end of the calculation.

31
00:02:15,630 --> 00:02:17,660
So my answer will be five, right.

32
00:02:17,940 --> 00:02:19,020
So it's very simple.

33
00:02:20,340 --> 00:02:24,990
You need to convert B, convert into the and old.

34
00:02:28,090 --> 00:02:34,570
Right, so Big Bird is not necessary to be present in the wordlist, it is given in the question itself,

35
00:02:34,750 --> 00:02:35,090
right?

36
00:02:35,170 --> 00:02:39,220
You can see it is not mandatory that begin work should be present in wordlist.

37
00:02:39,460 --> 00:02:46,960
But all the intermediate rewards, all the intermediate words, including the N-word, must be present

38
00:02:46,960 --> 00:02:50,350
in the wordlist and in one step.

39
00:02:51,260 --> 00:02:54,320
In one step, you will change only one character.

40
00:02:55,330 --> 00:03:01,980
We need to return the minimum number of words that represent present in the shortest transformation

41
00:03:01,980 --> 00:03:02,610
sequence.

42
00:03:03,180 --> 00:03:04,910
So I hope you understood the question.

43
00:03:05,370 --> 00:03:07,000
Let's consider one more example.

44
00:03:07,740 --> 00:03:16,350
So if you see in this example, example to the end of our lives, basically COAG, but the N word is

45
00:03:16,350 --> 00:03:21,270
not present in the wordlist since the end, it is not wordlist.

46
00:03:21,810 --> 00:03:27,420
We cannot have a transmission sequence since we cannot have a transmission sequence.

47
00:03:27,430 --> 00:03:29,010
The output is zero.

48
00:03:29,700 --> 00:03:29,980
Right.

49
00:03:30,150 --> 00:03:38,310
So now the question is how we can solve this problem so we can easily solve this problem with the help

50
00:03:38,310 --> 00:03:39,510
of BFC.

51
00:03:40,830 --> 00:03:47,160
We can visualize this problem as a grave problem and we need to find out the shortest distance, short

52
00:03:47,160 --> 00:03:48,670
distance and we can sequence.

53
00:03:49,020 --> 00:03:53,230
So let me show you how it will look like, for example, you have had begun.

54
00:03:53,460 --> 00:03:53,820
Is it?

55
00:03:58,160 --> 00:04:03,740
Now, the next number can be this one hot.

56
00:04:06,980 --> 00:04:18,399
The next note will be darte, then next Nade will be dog, and the last night will be COAG, right?

57
00:04:18,529 --> 00:04:23,510
So each in order will store some values what each inaudible store.

58
00:04:23,520 --> 00:04:26,750
So it will store one at the store.

59
00:04:26,750 --> 00:04:29,730
Two, it will start retail store for it will store five.

60
00:04:29,990 --> 00:04:37,490
So what we need to do, we need to just do before this before be a level of traversal and finally return

61
00:04:37,490 --> 00:04:38,270
the value.

62
00:04:38,270 --> 00:04:38,690
Right.

63
00:04:39,860 --> 00:04:43,640
So this is BFE problem, right?

64
00:04:43,730 --> 00:04:45,860
Finding out the shortest distance problem.

65
00:04:48,070 --> 00:04:56,350
Now, the question is from how I'm able to reach her, so the answer is I will go to every possible

66
00:04:56,350 --> 00:04:56,620
word.

67
00:04:57,010 --> 00:04:59,350
For example, what do I mean by every possible word?

68
00:04:59,350 --> 00:05:02,860
See, I have heard here what I am doing.

69
00:05:03,550 --> 00:05:13,480
I am standing at the edge, so I will have 25 possibilities of replacing the word each word in English

70
00:05:13,480 --> 00:05:13,930
alphabet.

71
00:05:13,960 --> 00:05:18,340
We have 26 characters, so I can replace it with 25 other characters.

72
00:05:18,850 --> 00:05:21,200
So I will get 25 different notes.

73
00:05:21,880 --> 00:05:26,550
Similarly, I will replace I with 25 other characters.

74
00:05:26,950 --> 00:05:29,290
I will get 25 other notes.

75
00:05:29,530 --> 00:05:35,190
Similarly then, for the last character, I will replace with 25 other characters.

76
00:05:35,500 --> 00:05:37,480
So I will get 25 other notes.

77
00:05:37,900 --> 00:05:46,810
But out of these notes, out of these new words, for example, I'm replacing Equidae and I get an old

78
00:05:46,990 --> 00:05:47,710
EIB.

79
00:05:48,370 --> 00:05:51,510
It must also be present in the World List, right?

80
00:05:52,300 --> 00:05:53,940
It must also be present.

81
00:05:53,950 --> 00:05:54,600
Never list.

82
00:05:54,610 --> 00:05:55,690
It is not present.

83
00:05:55,690 --> 00:05:57,190
So I will discard this note.

84
00:05:57,460 --> 00:05:59,770
Similarly, I will discard most of the notes.

85
00:06:00,280 --> 00:06:02,560
Similarly, I will discard most of the notes here.

86
00:06:02,560 --> 00:06:06,100
I will discard most of the notes here late.

87
00:06:06,310 --> 00:06:15,850
So when I will replace I with or so I will get one note at jotty rate and heart is present and the wordlist.

88
00:06:16,060 --> 00:06:17,860
So I will not discard this note.

89
00:06:17,870 --> 00:06:22,750
I will consider this note and I will do, I will increase the distance, save the distance.

90
00:06:22,750 --> 00:06:25,590
For this is one that I will do dist. plus plus.

91
00:06:25,600 --> 00:06:27,340
So the distance will become too.

92
00:06:27,790 --> 00:06:30,370
And in this way the next time.

93
00:06:30,370 --> 00:06:32,800
But you have, you have heart again.

94
00:06:32,800 --> 00:06:35,740
You will try to replace each with 25 other characters.

95
00:06:35,740 --> 00:06:39,250
You will try to replace all with the firefighters character.

96
00:06:39,400 --> 00:06:40,540
You will try to replace.

97
00:06:41,110 --> 00:06:46,300
And again, you will get many, many nodes and the most other nodes will get rejected because they are

98
00:06:46,300 --> 00:06:47,650
not present the novelist.

99
00:06:47,840 --> 00:06:51,510
So in this way, you need to construct this graph.

100
00:06:51,880 --> 00:06:57,520
And finally, when you will be able to reach the end world, you will return the value five.

101
00:06:58,900 --> 00:06:59,310
Right?

102
00:06:59,770 --> 00:07:02,140
So that's how you can solve this question.

103
00:07:02,440 --> 00:07:05,150
I know this question is a little bit difficult.

104
00:07:05,170 --> 00:07:05,770
That's true.

105
00:07:05,770 --> 00:07:07,360
This question is a little bit difficult.

106
00:07:07,630 --> 00:07:11,410
But we have already started to question using the fifth rate.

107
00:07:11,590 --> 00:07:15,590
We have solved this night's problem and will also solve this by animatics problem.

108
00:07:15,610 --> 00:07:23,350
So what you can do, you can just copy the code from here and paste the code for this problem statement

109
00:07:23,350 --> 00:07:24,820
and try to modify the code.

110
00:07:25,450 --> 00:07:31,510
So I will be doing I will be modifying the code in the next video, but I highly recommend that you

111
00:07:31,510 --> 00:07:37,030
use the best algorithm, use the existing code and try to modify their code so that that code will work

112
00:07:37,030 --> 00:07:37,300
here.

113
00:07:37,480 --> 00:07:37,930
Right.

114
00:07:38,690 --> 00:07:42,280
Ultimately, I will also do the same in the next video.

115
00:07:42,670 --> 00:07:45,760
So, yep, that's all that I want to cover.

116
00:07:45,760 --> 00:07:48,520
So I will see you in the next video with the solution.

117
00:07:48,520 --> 00:07:50,260
So this is all about this device.

118
00:07:50,560 --> 00:07:51,250
Thank you.

119
00:07:51,250 --> 00:07:51,730
Bye bye.

