🚀 Add to Chrome – It’s Free - YouTube Summarizer
Category: N/A
No summary available.
00:00
hey everyone welcome back to the channel i hope you guys are doing extremely well in the previous videos we solved the word ladder problem one and the word a ladder problem too but you would have seen this the solution
00:16
that we wrote in the word ladder too when you tried to submit and submit it on lead code it was giving you tle right why did that happen so first of all if you're just preparing for interviews you can skip this video do not watch this
00:32
particular video if you're preparing for interviews it's of new use because for interviews the approach that i have taught in the previous video for the world added to that is what you need to tell in the interview do not try this i'm just uh teaching you this so that you have some extra uh sense of
00:48
observation and sense of way like problem solving gets i'm just teaching you because i want your problem solving to get improved so first of all uh lead code the solution that i taught was accepted till a certain interval after that they changed
01:04
the test cases and the time limit was stricter so apparently uh the solutions most of the solutions on the discussion forum are giving you tn okay and the only way to solve this is i went through a lot of discussion forums a lot of threads and
01:22
the only way to solve this is break the problem and solve it in by using a hack which you usually don't need don't do it interviews so you're going to follow the cp way of solving this okay competitor so we're going to solve this the cpu way so if you're just preparing for interviews please please
01:38
drop off please that is my earnest request because at the end of the video you will be like i'm gonna teach something related to like cp way so the explanation might be faster something like that so how do we solve this problem it's very simple we're gonna break this
01:54
problem into two steps so what is the problem hit to cog and print out all the ways in which you can convert from hit to you have to print out all the ways that in which you can do it so the step one is
02:09
follow ladder remember this follow word ladder one and find the minimum steps that is the step one [Music] and store the steps for every string like store where
02:26
every string occurred on the left i'll tell you okay that's the step one so let's quickly do the step one for this particular again i'm assuming you have seen the previous two videos so i'll be going super fast so we know this is uh the beef is queue so where do we start we start from hit
02:42
right so this time what you'll do is instead of storing comma one instead of that what you will do is you will probably uh store some map data structure in that you can have it something like okay hit is initially zero that is what you will
03:00
do okay done so take out it so you'll take out it what can it be converted to try to convert it so it will be converted to hot uh is that possible is it possible to convert it to anything else have a quick check and we see that it is not possible
03:16
so it will be converted to hot so what you'll do is you'll put hot into the queue at the same time you will store it into the map as one more because at step one you got it right so done next you get hot so what you'll do is you'll take hot and you'll be like
03:32
okay we have a hot so let's try to convert hot into something so when you try to convert hot into something you'll actually get dot and you'll get locked so you'll get dot and you'll get lot by the way make sure you remove for hot and dot and
03:48
so you got dotted so dot you got at the second level and the lot you got at the second level perfect done next time please take the next one dot so when you take dot out you try to convert it and you can actually convert
04:04
it into dog can you convert it to something else i don't think so so you'll take the top and you'll put it into the queue at the same time we will say dog to have a three in the map so dot is done next thing please take out lot so when you take out lot what you'll do
04:20
is you'll say okay lot will be nothing but can be converted by the dog is done lot can be converted to lock right so you'll be like okay log and this log is at how many steps lot was at if you see lord was a 2 so this will be
04:36
also at 3 perfect so this is also done log is also done next take the dog out and what is dog 3 the dog can be converted into dog can be converted into cog so convert it to cog it will be level 4 and you'll put that into over
04:53
here and then erase it next you get the log again and this time lock cannot be converted so done next time you'll get caught it cannot be so the queue is ultimately empty and this is the
05:09
you can store it in any structure that you wish to i'll really store it in a map data structure done right so step one is done step one is very simple and we figured out that the minimum number of steps that we required was four or the sequence length was five so
05:25
let's ease this now that series everything so that was step one step one stated get me the minimum steps and we saw that the minimum step was nothing but four in this case so just go ahead and store it
05:41
so the minimum step was four that means four transformations step one is completed another step two back track i repeat back track in the map [Music]
05:57
back track in the map yes from end to begin to get the answer [Music] now you might be thinking but trevor why from end to begin i'll give you that explanation but you first need to
06:13
understand the algorithm i'll give you the reason why and to begin but right and then but before that you need to understand the explanation in depth so you have seen what is the step two from the end to the beginning so what i'll do is fine i'll say i'll do a simple enough
06:31
dfs calls from the comp with saying the sequence contains cog we're going to travel in the backward directions so what can be cog converted to can be converted into a lot of things right so we try to convert cog
06:46
the only valid things that are there in the world list or in the map are log or dock i can convert cog to log or dock do you agree with this or not you do right so lock and dock
07:03
can we convert this into can we convert this cog into something else we probably can but we will only have two options which is the lock now while converting if you're trying to convert it into log you know the cog
07:20
was at the level four so the conversion that you're doing is a lock it has to be at level three it has to be at level three is log at level three it is it is there at level three they'll say yes possible
07:35
log and then the sequence will be cog and log perfect another dfs or another chain that you can do is dfs of i said dog as well dog and this will become
07:51
cog and dog now kev is dog possible let's see this was for dog is three possible right before the level right before the level we actually encountered it so this is possible it's a couple of dfs calls that you can do you can try
08:07
out changing cog as you did and then you can call these two dfs calls first this will be executed according to recursion then this will be executed if your recursion is weak please please go back and use the recursion series so this is something which you have picked
08:22
out next we have a lock right what can we lock converted to lock can be converted into a lot of things like lot dog again and can we convert it into a lot of other things as well now log can be converted into doc but what
08:40
is the value of log the log's value is three the dog's value has to be two but we see that the dog's value is three and the logs value is three as well so it cannot be converted back to dog this is how we stop extra conversions or unnecessary we
08:58
just follow the right path because we just want to move where the conversion is so that's not possible so log will be like okay can i be converted into lot i'll be like yes why because if you convert the g to t log can be converted into lot
09:14
why because this was three and lot was two so this is right before this conversion so lock can be converted or traced back to plot this is nothing but simple backtracking so this is like cog [Music]
09:30
log and a lot perfect right next what can be not converted to lot can be again converted into a lot of things but what's the value plot two so when we try to convert it into something like
09:45
let's say locked trying to let's say we try a lot to dot is this possible yes l can be done to d but what's the value of lot 2 and what's the value of dot 2 so lot
10:01
cannot be converted into dot because they're of the same level you're backtracking you're backtracking so lot was two it'll try to convert it into hot yes defers off hot which is called
10:17
log lord and hot perfect so we are at hot now the moment the call comes too hot the moment they come call comes too hot hot will not try to convert itself or will not try to convert itself and we'll try to convert it itself to a lot of things but the
10:34
only possibility will be dfs off hit y because the hit is at 0 and hot is at 1 1 before that so that is possible so we see the new one will have clogged log lot hot and hit
10:51
now the moment this dfs call is meet the moment this dfs calls me we get a hit which is nothing but the beginning world the moment you're getting the beginning word the moment you're getting the beginning word you're like we have got an answer and if we have got
11:06
our answer we say fine this is a particular answer so we like we can store this in our answer one of them so go back go back go back go back because there were no further things execute this and again go and execute
11:23
execute execute and you'll again get another sequence which you can actually put it into the answer which you can actually put into the answer no why did this run the first reason is while we did the previous solution we were actually storing sequences
11:39
which ended up resulting in tla because imagine imagine you want to go from a point to another point right and you're trying a lot of possibilities and then you figure out that there's only two possibilities to reach there
11:56
you tried out a lot of possibilities a lot of them but you figured out that there were two correct possibilities to reach there right so what did you do in the step one at first you figured out the shortest path so when you figure out the shortest path you don't need to
12:12
store the sequence which was consuming a lot of time just did a simple dfs on the queue according to step one as you did over here and you easily yes you easily were able to store this thing who were at which level
12:28
level zero was this guys level one is this guy level two where these guys level three whereas these guys level four was this guess you are easily able to store that right so we know one thing that we have stored that and we did not require to store the sequence now if you
12:44
try to figure out the sequence starting from the start you'll actually explore a lot of parts but if you try from the end then you know there are only two paths to explore so the exploration of paths will be minimal when you start from the back
12:59
because on the back there's only some answers like for an example you're having a four so when you start from back you know there will be lesser amount of answers there will be lesser amount of answers i hope that makes sense because over here you see a lot of things like it goes to
13:16
heart in a lot of examples there might be a lot of other words in the level which will not lead anywhere which will not lead anywhere like you might convert it or too hot it to let's say him
13:31
him to dim and then hot goes on and gets the answer and this dim did not go anywhere but this will still be in the map this will still be in the map so you don't want to explore these parts unnecessarily that is why step 2 says that is why the intuition of step two is
13:49
start from the end to the begin so that you unnecessarily stop exploring the extra parts you know there are two parts you know there are two parts you'll only explore two parts so you'll only carry two sequence you'll only carry two sequence throughout the
14:04
throughout the journey so unnecessarily carrying of sequences will be reduced which indirectly saves a lot of time but gender actually saves a lot of time again this is a lot of cp stuff if you are into competitive programming this will be cake for you
14:21
you're just into interview preparation you might find this stuff [Music] so guys i hope you understood the explanation because that is where the gist of the solution lies understanding step one and step two in depth so since
14:36
we are dealing with tl issues i'm not following the interview standards of not declaring anything global and all these things i won't be following that okay so q string of cube that's the first thing builder map so i'll declare it over here
14:52
unordered map of string this will be storing the distance so i can probably say q dot push of the begin word that's something which i'll do once i've done this what's the next
15:07
thing that i'll do i'll say okay begin word can be said to have a zero thing i can see that now or i can mark it as one that is your choice you can keep it as zero or one whichever you wish to next i'll say okay let's start off the queue
15:24
what do you do in the queue that's very simple the same thing q dot front get it pop and now what you can say is okay fine this is what we have got now we need to traverse and change every character so let's traverse in the word so i equal to zero again please make
15:41
sure that we don't write this usually in c plus plus it does store it like it just computes it once but still not take a risk i'll probably compute the size over here because i want to be absolutely sure sure that it doesn't gives me tealy i'll
15:57
do all the optimizations that are possible from end so this is something which i'll do no more repetitive calculations of dot size again and again so care of original equal to phi and when we come back word of i equal to orange so that all the changes have
16:13
reverted next i'll do a character ch equal to a character less than equal to z plus plus that's the first thing we'll do right next i know one thing what if i will dch perfect i'll try to see okay fine our
16:30
list i need to quickly check how do i actually check here so quickly do an unordered set so what let's do our begin like this dot word less dotted that's the first
16:46
thing you'll do next let's have a quick check if it does exist or not so i'll be like okay fine sir do you have this word whatever it says yes i do have which means it will be a greater than zero value is that you i have this rule can you please take it
17:02
i'll say map word well be answer i'm like this is a new word right and the previous word had some value really i can keep the steps equal to mpp of word because that is where i'm storing it i can say mpv of sorry i can have this steps plus one
17:18
so i store the steps over here perfect this is how i can easily store the steps once i've stored the steps i know everything is stored in this map i just need to backtrack so i need a vector of vector string as an answer so i'll store
17:33
it here only and i can return the answer here again declaring everything globally so what you'll do is okay remember one thing you need to find the answer right you need to find the answer so if in case just make sure also please make sure you
17:50
erase it from the set it's very important that you raise the value otherwise you will reiterate on it okay what's the next thing once you've done everything what is the next thing that you'll do you'll just quickly check if you actually reached there so justin key is like you
18:06
reached the last guy which is end wood that's fine like it should not be equal to end that means you reached it and the map is storing a value if you reached it it's perfect call the dfs from the end word and have the answer and if it doesn't gets called then you return an
18:23
empty list as the answer now let's go back and write the dfs well i'll quickly do a private function for dfs now string word i can carry a sequence over here so i'm not sure if this will clearly but let's give it a try
18:39
string sequence and against the sequence dot push back if it gives a dle what we will do is yes very simple we will just go across and uh do it at a global variable so sequence has been passed over here so please make sure you
18:54
always carry these things in reference as a sequence perfect now if this word is equal to begin word so again i don't know do a lot of these things so i'll just go across and
19:11
say we can vote so if this is b which is the beginning word i say we've got our answer and this can be a part of our answer which is the sequence and i can return this is where the recursion ends otherwise i go across and do the same thing which
19:28
is character change i go across and do the same thing which is character change right and coming vectors same thing again but over here we are trying to backtrack you need to understand we need to we need to backtrack and in order to backtrack we
19:44
have to check okay we're going back to a word we're going back to a word which is word of i equal to ch so the word has changed i need to check okay this is this word in the dictionary that's the first thing that i need to check let's quickly have a check is this all
20:00
in the dictionary which is nothing but your map data structure whether we what's map declared as mvp yeah so i'll be like okay cool i'll go like mpp.find of the word if this is
20:16
in the dictionary that's the first thing if this is in the dictionary the next thing that i need to check is okay you guys you are in the dictionary now do you have a value do you have a value which is exactly lesser than my word which is lesser than my unique i need to
20:33
check it how do you check it firstly probably you can store the steps in some variable like this now let's have a quick check if this plus 1 is equal to equal to the steps that i'm looking for because this is the word
20:49
that i i'm going to go back one step back so plus one should be equal to steps if that is the case you are fine you can go and do the dfs with a new word and with the new sequence okay new sequence what does that mean this word will be a part of your sequence
21:04
isn't it so you'll say okay this will be but when you come back you need to take it back because the next step you don't want the word to be added simple basic backtracking this is what you do and whenever you push back the answer make sure you reverse
21:20
because as of now the answer is stored from end to begin and you need to store the answer from in the opposite direction this is how you will compute the step two so before compiling this code do you think that there is an error there is an
21:37
error now you are reversing the sequence over here storing it into the answer but the recursion doesn't wants that the sequence is disturbed because you have to go back and when you go back you have to do a pop back so the wrong guy will be popped back so make sure you're
21:52
reversing it to put it into the answer but you re-reverse it before returning simple basic record so before submitting this code there are some minor mistakes that i have done so first of all when you're using the begin you need to yes this is this is a mistake and the
22:10
other thing is uh once you reach the world just to optimize once you've reached the end word there's no need to do anything because you've marked all the levels and your job is done so these are the two things that you need to add it and once you've done this try compiling this and it should
22:26
give us a correct answer yes it does now let's quickly try to submit it now you must see that okay i've tried it a lot and i figured out okay okay faster than 99.96 though i do not believe on lead code these things so this is how you can actually use some
22:42
trick like this is a hack because the standard way is the one that i have taught in the previous video that is what you have to tell in the interview don't be over smart and don't tell this one there's a lead good purpose because a lot of people do solve lead code they want their problem solving skills to be
22:58
right up there so this is a problem where you learn various methods of problem solving and i absolutely loved this problem so i hope i was able to explain you this tough problem so just in case i was please please please make sure you like this video and if you're new to our channel
23:13
i think you should definitely subscribe to us because i do put up a lot of content which is related to ds algo and lead code as well so if you haven't checked out our dp series and the hd sheet i think you're missing out on a lot of stuff the links are in the description with this i'll be wrapping up this video let's meet in some other video till then bye take care
23:30
whenever your heart is [Music] you're broken