🚀 Add to Chrome – It’s Free - YouTube Summarizer
Category: Algorithm Tutorial
Tags: algorithmBFScodingprogrammingtransformation
Entities: BFSC++QueueSetWord Ladder
00:00
hey everyone welcome back to the channel i hope you guys are doing extremely well so in this video we are going to solve this word ladder one problem which is an extremely hard problem so what does the problem state the problem states you're given two
00:15
distinct words two distinct so a start word and a target word and a list denoting one list of unique words of equal lengths find the length of the shortest transformation sequence from start word
00:31
to the target word now you need to keep the following conditions in mind a word can only consist of lowercase characters only one letter can be changed in each transformation very very important each transformed word must exist in the
00:48
word list including the target word the start to word may or may not be part of the word list so what does uh this particular problem define so it defines a given a begin word so over here it is hit given an end word over here it is
01:05
cog and you are given a word list which will be containing certain number of votes and if you see all of them are of length three so if i start with it so let's start with something like hit now what you can do is you can change any one of the
01:22
character like there are three characters in hit you can change h you can change i you can change t you can change any one of the characters of it so as you might say that hey i'm going to change this i to o so what i'll get is hot and if you carefully see hot is
01:40
there in the world list so you can have this transformation done in the next step i say i'll change hot to dot which means i'm going to change this h to d and if you see dot does exist over here in the next i say i'm going to
01:55
change dot to dot basically i'll change t to g which is dot to dot and if you see dog also exists in this particular word list in the next i'll say i'll change talk to i'll change the d and i'll make it c and
02:11
i'll have a comp which is nothing but our end word if you carefully see this is nothing but our end word so if i ask you how many transformations did you do there was like one two three four and what is the sequence length that's five
02:26
so thereby i can say that this is the shortest transformation sequence if you wanna start from hit and you wanna end at something like a so if i show you one more example over here we have the world list as des dr dfr dgt dfs so
02:43
dr can actually be changed to dfr and dfr does exist if you see and then dfr can be changed to dfs and dfs also does exist over here so over here the sequence is of length three thereby the output is three now it
02:59
might now what if it is not possible to change a particular given word to any other word in that case you will just return zero stating that it is not possible the sequence length is zero now you must be thinking which algorithm to apply but before going into that direction let's
03:15
analyze the problem we are given hit right so what can we do to the set so hit is getting converted to something like hot where the eye is changed to oh right so the second alphabet in the world is changed so if i
03:32
say hit [Music] where can i change you can be like striver i can change the first h driver i can change the second i striver i can change the third t make sense
03:47
now let's go deep if i ask you if you change h in hit what can you make hs you'll be like i can change h to ait make sense i can change edge to vit makes sense i can change h to cit does
04:06
make sense i can change h to d i t make sense i can change h to rit makes sense i can change h2 zit sorry zit does make sense so apparently in the head i can pick up the first character and i can
04:23
change it to anything from a to z do you agree i you do agree right similarly can i say i can pick up i and i can change it to anything from a to z do you agree in this
04:39
you have to and when i change i to o i get hot and that hot does exist over here if you see the hot does exist separately you can try changing like h a t h b t h c t het hft
04:57
but the only one valid will be hot why because that exists in the old list and the next step you can be like i can change t as well t can be changed to a to z and the what has to be in the world list agreed so
05:14
this is the brute force that we will follow we will start with the particular word and we will try changing it on character to character and every character we will replace from a to z and we will see if it is in the word list or not got it so as of
05:32
now you know the brute force right so if you know the brute force the brute force is pretty simple you have hit you take h and you try to change it from a to z you take i you try to change it from a to z you take t and you try to change it from
05:47
a to z and you count the minimum lengths yes you count the minimum length because the question states you have to find the shortest transformation sequence so you have to change it in such a way that you find the shortest transformation
06:03
sequence now which algorithm to apply if you are willing to find the shortest sequence let's analyze that so if i say i will keep the hit as the level one right at the top
06:18
according to brute force i'll try to do h to a i t b i t c i t d i t and so on till z id i'll try to do this right in order to transform hit to any of
06:35
these in order to transform it to any of these these words should exist in the world list and they do not if you go and see in the word list there is nothing like ait bitcit none of them so not possible next i'll take i
06:51
and i'll try to change it from a to z so i'll get like h a t h b t h c t dot dot so these are all the words that i can change head to and apparently only hot
07:09
does exist if you go and see hot is the only one that exists over here so i can say from hit i can go to hot now i'll take t and i'll try to change it to h i a
07:25
h i b h i c so on to h i said let's see if they exist in the world list none of them yes none of them do exist in the world list so that is not possible so only hot is possible can i say this
07:40
is the second step because the length of the sequence will increase to two perfect now i have a word as one i'll again perform the same thing i will take h i'll try to do it like aot bot cot
07:55
d or t and so on till zot and i'll see only dot exists only dod exist if you go back and see only dot exist and lot also exists and d o t and lot also exist so if i change
08:13
this to dot and i can also change it to lot so that's when i change h let's see for o h a t h b t c hct hdt and so on till h z
08:31
t does anyone exist let's have a quick check no one next let's try to change t that will be [Music] and so on does anyone exist have a check
08:47
hot does exist hot does exist because if i change this t to t hot does exist but you will not take that into consideration why it's the same word it is the same word so you do not take that into consideration because
09:03
there's no point in going to hot again and going to hot again or there's no point in getting to hit again i can change this o to i as well and i'll get h i t but if i've come down from hit to hot is there a point in going back to it because that will only elongate the
09:19
sequence so apparently this is the step three similarly i can take dot and i can do the transformations similarly i can take lot and i can do the transformations and this will be level four similarly i can just go on doing the transformations and this will
09:35
be level five since we are going something like a level something like a level whenever whenever assume somewhere over here we reach the particular cog we reach the particular cog
09:51
can i say the length taken will be five and that will definitely be my shortest sequence can i say this i can why because beyond this since i'm doing level wise anyone
10:07
that will be level six the length will increase so i'm definitely sure i am definitely sure whatever i'm getting over here that's the first instance of cog it might come over here again but length five is what matters so the first
10:22
time whenever we encounter the end ward that is when we end which traversal is this which traversal is this guys yes yes yes it is nothing but the bfs traversal so we go ahead and apply bfs traversal to this in order to solve this amazing
10:39
tough problem so you saw how i started the problem using simple brute force then i analyzed the brute force and figured out that we can apply bfs algorithm that's trying to do a dry run on this particular example so that the algorithm gets into your head straight away so
10:54
you know that this is the beginning word and in a bfs algorithm we always start with a q data structure so what i'll do is i'll just take the sword and say hit comma one because the length of the sequence as of now as one so you have taken that and put that into the queue data structure the next thing that i'll
11:10
do is i'll take this out from the queue data structure and i will start working on it so as of now we have a word hit and we have the sequence length as one right now what i need to do is i need to take h and change it to a which will make it ait
11:28
and then i'll check does ait exist in the world list now this is an array if i go and do a linear search and check that is definitely going to take a lot of time so what i'll do is i'll take a set data structure and i'll make sure
11:43
that the same thing yes the same word list does exist in the set data structure so that whenever i change this edge to a and make it ait i can easily check in the set data structure if they exist or not in a very very less time
11:59
complexity so ait doesn't exist then i'll make it bit that doesn't exist then i'll try c i t d i t e i t so on till zit none of them does exist next i'll move to the next alphabet i
12:15
and i'll be like h80 does it exist no hbt does it exist no hct does it exists no hdd doesn't exist no i'll keep on doing and at h o t when i convert this i to o when i convert this i to o i see
12:31
hot does exist case i see hot does exist over here so what i'll do is i'll simply take this and convert this to t like oh and that will be sequence length of two so i'll put that into the queue data structure saying this is of a
12:48
sequence length two right so hid got converted into a hot weather sequence length of two now do you keep the hot in the set data structure do you the answer to that is no because if you remember in a bfs
13:04
algorithm whenever i visited the notes whenever i visited the notes i used to mark them as visited but over here we are not using anything such as visited so what i will do is i'll say okay we got taunt so we will remove it from the set data
13:20
structure now you might say but strava what if we get this in a future let me come back and explain you this with a very trivial example imagine in order to go from orissa to kerala there is only one particular way okay there is the shortest way because from orissa to
13:37
kerala there will be one shortest way and the shortest way will have a length of three secrets right so tell me one thing from kolkata you went to orissa right and from there you'll take a distance like a sequence of three to reach kerala
13:54
right so if odyssa is on the level two right will you take orisa again in some other levels for an example from kolkata you went to bangalore and then to odessa
14:09
does it make sense to take odessa in this third step because you've already taken is in the second step and you know from the second step that is the minimum that it will take and even if you start from what from here it's again going to take three
14:24
so if before you have got orisa before you have got redesigned you're taking three after you're getting odyssey again taking three that's better now once you've taken orisa there's no point in taking again afterwards because the lengths from modista to the
14:40
last guy is three so if afterwards you take it's already a lengthier guy so it's better you do not execute orisa in the future so similarly i can say something like hot i'll not execute hot anywhere in the future because if i got
14:55
that in the second step or second level there's no point in encountering them in future levels because from here i can travel wherever i wish to going from further levels will actually increase the length right
15:11
done next i'll try to convert i to everything else till h z t but nothing will be there next i take t and i try to convert it so h i a h i v h i c
15:27
h i d so until h i z none of them is in the word list so we do not take so we just got one and we have inserted that into the q data structure time to offer the saw next take the next guy from the queue
15:42
data structure that is hot with a sequence of two so as of now i can say where can hot go let's analyze so we need to change h be like a oh sorry e o t b o t
15:58
c o t d o t so on till z o t and you'll get dot and you'll get plot you carefully see you get lot and you get dot so you can actually go to dot
16:14
with the step 3 or you can also go to lot with the step 3 because both of them do exist so when you go to dot you just erase it and you put them with three and when you go to lot you raise it and you put them with a three
16:29
so since we can go to dot and not we will remove them dot is removed and i'll put that into the queue next i'll get lot so lot is removed and i'll try to put that into the queue data structure so can i do anything else let's uh try it out we can change this o
16:46
so h a t h b t h c t h d t h e t and so on till x t none of them is there so next i'll change uh t h o a h o b
17:02
h o c h o d h o e and so on till h o z none of them is there next nothing so what i can say is we got it so this traversal of the queue is complete what
17:19
is the next thing let's get dot of three so dot of three now let's try to change again so we have d let's try to change d so it'll be like a o t b o t c o t like d ort until z o t
17:34
none of them does exist in the word list next i'll change o so i'll get like d a t d b t d c t d d t d e t none of next i'll try to change t so it'll be like d o e
17:49
d o b d o c d o d and so on d o g so dog does exist if you carefully see dog does exist so what i will do is i'll take that yes i'll take the dog [Music] so i'll take the dog with a step four
18:07
and i'll try to insert that into the queue data structure with a step four what is the last word it was log not dot so done nothing else is possible next take lot3 outside let's see what can we make lot3
18:25
let's try to change l aot nothing possible let's try to change oh lad lbt lct ldt so under lzt nothing is possible next t
18:42
l o a l o b l o c l o g log is there log is there so you can take it to l o g but step four removed log with step four
18:59
perfect next dog of four [Music] dog of four so as of now can i say if this is dog of four thereby when i try to
19:14
change this d i mean like a o g b o g c o g and we see c o g is present here so we insert cog with a five step you can stop over here but i generally do not
19:32
i just want to explain you so cog5 is there done cog is removed now this is the point you'll understand someone reached c o g with five someone reached c o g with five but the next time when the q tries to get this up l o g four and tries to change it it
19:49
will actually get something like cog it'll actually get cog because of this l when this l gets converted to c it will get cog but there is no cog in the world list because you've already encountered cog because you've already encountered cog this is what i was trying to explain
20:05
once you have got someone it will take its path why will you again visit that path so this is how the set helped you if you erase it from the set there will be no further occurrence of like cog5 otherwise you'd have taken cg5 again and would have kept on going so that is
20:21
how the set helps so log cannot be made into anything next time when you do an uh extraction from the queue you get cog with five so your end word or c or g the word that you get from the queue is cog and the steps that it took was five so
20:39
your answer boils down to five yes your answer boils down to five and this is the answer that you will return and imagine if the cube becomes empty you have tried out all possible changes and you never ever reached the
20:54
end word during the extraction from the queue then you can after the end of the queue you can return 0 which will be your particular answer so you have figured out what is the algorithm that is required to solve this complex problem so i'll be coding the c plus plus in the right and if you have
21:11
anything tactical issues related to java you can watch it out on the left so we have a start word we have a target word and we know we need a queue which is going to store a pair and the pair will be having a string and an integer this is the queue that will be defined and we
21:26
know we always start off with the start toward and the sequence length is one and we know there will be a set right and this particular set will always have this particular target word so it's uh sorry the word list so you
21:42
can always write something like this in c plus plus it's a very simple thing you can just write this and that will take the entire vector and put it into this particular set data structure you can use the unordered set it takes amortized time complexity of uh
22:00
one big of one but the worst case is still being co-open but the amortize is we go off one so we'll be using an ordered set now you remember whenever we pushed something into the queue we marked it as visited so we can always use visited as
22:15
deleting from the set so we can say that okay can you please go and delete start one so if it exists it will delete the start word from the set this is done what's the next thing the next thing is very simple we say we will iterate till the queue is not empty so go ahead wait till the queue is not empty done what's
22:32
the next thing that you do you say okay give me the word so can i see the word will be very simple q dot front dot first i organized these steps or the length will be very simple again q dot front dot second once you've got it from the queue can i say q dot pop is what you'll say take it
22:49
out of the queue now every time you get a word for every character you're doing a change for every character so what you'll do is okay for every character i'm doing a change so can i actually travels to all the characters i can so let's traverse to all the character
23:04
which is something like this right now every character is nothing but can i say uh the character alphabet or original there's nothing but modified this is the character that i'm looking to change so can i say what am i looking to change
23:21
i can change it from a to z so can i see i'm looking to change it from a to z this to this to this so every character what i is what i'll replace so i'll say would i can you get
23:38
replaced by ch every time it comes up it gets replaced by a new character first time let's imagine the word as just imagine though what do we had okay so what will happen is for the first time original we'll have something like h right so this what i will be like
23:55
instead of h it will be having for the first time a80 next time b80 next time c80 this is what the internal for loop will do is this is what the internal for loop will do so you will be changing the values you'll be changing the values now
24:11
what is does that value exist in your set so you'll be like okay center find does this word exist and if it does exist then it will never be equal to n because if it exists it will always like if it doesn't exist it will be pointing
24:27
to it this means it exists in the set it is the count as well uh so done what's the next thing that you'll do if it exists what way are we doing we're saying okay say market is visited which means do this
24:43
tell the queue this guy is there with an increase steps done once you have pushed back into the queue make sure you replace it with the original y because over here you're always changing so the last moment the
24:59
word why what i will always have z or z so you need to make sure that it gets back its original value so this is what you'll do right and over here can i say every time you're getting a word can you just go and quickly check if
25:14
that is the target word if that is the target word can i say these are the steps that i'll take again you can write it over here as well over here also you can have a check but i usually prefer keeping it over here and then we can return a zero saying in case it did not find in case it finds it
25:31
in return the steps otherwise a zero this is how simple the code is so if compiler it is working now let's quickly try to submit this so when we submit it is running absolutely fine so this is how we can easily do this particular
25:47
thing and you might uh ask me about the time complexity and something i know for sure is whatever the word length is word length into 26 these things are running for what length into 26 like whatever your word length is
26:03
because they have already stated all the word lengths will be same so whatever is your word lengths into 26 is the internal loop now how many transitions will you do how many transitions will you do at the worst case you can do a lot of transitions but
26:21
if you carefully think can i see the number of transitions can i see the number of transitions you can carefully see one two three four five six one two three four five six can i see the number of words over here will be
26:38
the number of times it will go into the queue at the worst case because if it is not in the set of words it never goes into the queue so can i say the queue will run for n times
26:54
the number of times the words are because that is only when it gets into the queue otherwise it will not go so can i say the complexity is n into word length into 26 every time can i see this i can definitely say that you're using any extra space yes you're we're using an ego of n space to store all of these
27:11
things into the set and by the way there's a logarithmic factor if you want to include it for set if you're assuming that your hash set works in big o of one but then you can use bingo of one over here otherwise you use a logarithmic if you're using something like a set you'll have a logarithmic
27:27
so depending on what is the time complexity of a set this can vary so guys this will be the time complexity and the space complexity for this particular problem i hope i was able to explain you just in case i was please please make sure you like this video and if you're new to our channel what are you waiting
27:43
for i think it's time that you hit that subscribe button and if you haven't checked out our dp series and the hd sheet and you're missing out on a lot of content the links are in the description please please make sure you check it out and yeah with this i'll be wrapping up this video let's meet in some other video till then bye take care
28:02
ever forget you're golden