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.