Breadth First Search | Word Ladder | LeetCode 127.

[@moshfizzle925]

That intro tho LMAOOOO!..keep up the good work bro! you bring life to Leetcode problems!

[@ik6071]

I’m struggling doing these questions and I’m starting to lose hope

[@NickWhite]

nooooo ! this is a medium problem! Do some easy ones

[@mh9215]

Keep at it, its difficult for everyone. The hard work will pay off :)

[@ansuman4233]

You will get there! Trust me. When I started off reading through questions like these a month ago, it was so overwhelming and when you keep doing(trying) to solve problems (starting from easy and upwards) your brain would automatically find the pattern. I don't how it works but that's true! A month ago, I would have never thought of doing a BFS on this array but when I started with this problem today, the voice inside my head automatically went USE BFS! Although my answer did not pass all the test cases, I was elated that I could think of an approach! I hope you get to read this and keep practicing and never give up! and thanks Nick, you're a rockstar!

[@varunrao2135]

learn fundamentals before doing random questions and feeling like u have no hope. every questiono has like 4 -5 underlying topics in it. learn those, learn the techniques do them well and come back to it.

[@nirmalkumarsahoo8683]

Thanks Nick.

[@akshaygupta4349]

Nick, Thank You for the video. It would be really helpful if you could also talk about the space and time complexity associated with each solution.

[@iamjiaji]

Line 22, should be c

[@NickWhite]

yeah that was an accident my bad

[@iamjiaji]

@@NickWhite Thanks for the solution!

[@IWantSoundKnowledge]

They updated the test cases on leetcode. Now they include 'z'

[@nehalshrivashtava1169]

@@NickWhite your LinkedIn URL is wrong I guess... btw thanx for this video

[@surajitpaul]

@@NickWhite Thanks for creating the videos, these hiccups actually help in learning process!

[@pubamx]

Hey man, I think you could save the first for loop by just declaring the set like this: Set wordSet = new HashSet(wordList);

[@willinton06]

Loop still there just behind the function, unless some pointer arithmetics are being used, doing the loop will save you some time

[@MehediHasan-tm8ek]

Thanks, Nick But I think loop will be *for (char c = 'a'; c

[@jeffreylee911]

for (char c = 'a'; c

[@karthikbhat181]

Hey Nick! In the 3rd for-loop, where you iterate over all the characters from 'a' to 'z', shouldn't it be from (c='a') to (c

[@johnnydoey7920]

Yea I tried his code out but failed one test case then I changed (c

[@Jing34271]

@@johnnydoey7920 you are the smart guy

[@terrypbark]

What is the time complexity of this?

[@ayushthakur-be2lr]

The char loop should be from c = 'a' to c

[@alekseidanilov9279]

hi Nick, thank you for video, great explanation. But why for loop from c = 'a' to c < 'z' (not inclusive 'z')?

[@NickWhite]

accident! Good catch that’s my bad!

[@sumitanglekar6309]

Thanks for clearing this out. I was struggling for a while when I decided to look into the comments for an answer!

[@tejasjain7097]

Test cases have been changed now fam, Don't forget the

[@PritamKarmakar]

Great explanation as always. Do you mind posting a video for Word Ladder II problem?

[@pradeeptiwari4193]

I did that last night - Exactly same thing but maintain the list of list of words already accounted

[@codewithjc4617]

I got this question on a Facebook Interview a year ago

[@tmzpanda]

2:34 bfs (queue + Set) Lintcode: www.lintcode.com/problem/word-ladder/description bidirectional bfs: kzbin.info/www/bejne/i3q6pGejZZxqf68

[@biswamohandwari780]

The first thing when i search for any leetcode question's answer is either Nick White's Solution or Tushar Roy's.

[@akshaywaghela8647]

Output is 0 instead of 10 for the below input. 42/43 test cases passed. "ymain" "oecij" ["ymann","yycrj","oecij","ymcnj","yzcrj","yycij","xecij","yecij","ymanj","yzcnj","ymain"]

[@Jing34271]

change (c='a') to (c

[@akshaywaghela8647]

@@Jing34271 it was a

[@nagalakshmichithambaranath1147]

You made the difficult to sound very simple to solve. Your videos are really cool. Thanks!

[@lakshaysharma8605]

Man, you are just awesome. Your Explanation of the question just hit the nail on the head. Keep Going !!

[@shreyamduttagupta7527]

any idea about the time complexity?

[@vanapallisuryanaryana8881]

def ladderLen(beginWord, endWord, wordList): if endWord not in wordList: return 0 queue = collections.deque([(beginWord, 1)]) wordmap = {} while queue: word, level = queue.popleft() if word == endWord: return level for hop in wordList: if 2 == len(set(hop).intersection(set(word))): if hop not in wordmap: wordmap[hop] = None queue.append((hop, level+1)) return 0

[@MistaT44]

The use of snake case and camel case triggers ocd. Haha but jokes aside, awesome video as always Nick! This was a tricky problem

[@TheDannyDeez]

Good shit nick, good shit.

shouldn't the condition on line 23 be: if (word_chars[j] == original_char) continue; ? It doesn't make much sense to me as it is.

[@andresalba34]

If I see this problem in an interview , I'll just get up and change careers 😅

[@heisenberg1844]

Thanks to you, I've mastered BFS. B)

[@MGtvMusic]

hahaha same

[@omkarvaidya6077]

Nice explanation. Thanks, Nick. It would be also helpful if you could discuss the time and space complexity of the solution at the end. Also, would appreciate it if you could post a video on Word Ladder II as well. Thanks once again.

[@tehAmaazingSheikh]

It would be nice to see the raw video with the mistakes so we could see your thought process when you reach a wall

[@raghuramanswaminathan5187]

Beautifully explained Solution Nick! Thank you so much.

[@gauravvarshneya6761]

Great explanation! One question though, why do you remove the word from the set? Wouldn’t you want to keep it since you’re not sure yet if that’s the path you want to take to find the EndWord? Example: .........”hall”>“ball”>”wall”>”walk” .........“hall”>”wall”>”walk” In the above example, if you remove “wall” from the set in the first line, how would the second line work since that should be the shortest path?

[@lifehacks9450]

Because in the first iteration The word wall would have been added to the queue so when we will pop out that word wall we will get walk and ans would be 3

[@mohammedsadiq1567]

Hey Nick, Will you please help me solve this one? Determine how "out of order" a list is by writing a function that returns the number of inversions in that list. Two elements of a list L[i] and L[j] form an inversion if L[i] < L[j] but i > j. For example, the list [5, 4, 3, 2, 1] has 10 inversions since every element is out of order. The list [2, 1, 4,3, 5] has two inversions: (2, 1) and (4,3). Do this in better than O(N^2).

[@NickWhite]

sounds like count inversions which can be implemented using a divide and conquer approach and can run in NLogN time

[@NickWhite]

just look up “count inversions solution” on google and you’ll find something

[@mohammedsadiq1567]

@@NickWhite Got it thank you.....!!

[@FabioLux]

Funny to see that they changed the problem difficulty from medium to hard

[@mostafamohsen250]

I think the first for loop in the while loop is unnecessary, wouldn't this solution still work without it?

[@willinton06]

Can’t you just loop through the words and have a counter of letters that are different? If the counter returns 1 you know it’s a transformation and if it returns more it’s just different

[@SolutionHunterz]

Thanks for posting videos, However it would be great to go over the different solutions and their time and space complexity. That would help a lot.

[@muskangupta7522]

can you also add 126 word ladder problem (hard version) , where we have to return the list of all sequences from begin to end node ...

[@arnabpersonal6729]

You can avoid the loop having 0 to size

[@andresm-pf9ij]

Hey Nick ty for the video, how this is ensuring this is the shortest path?

[@tathagatnegi5923]

Congrats for the 80k buddy👍.. 100k soon

[@spectermakoto9029]

Do you really gotta cycle through the entire alphabet just to solve this problem?

[@mastaharashibu7092]

I was thinking the same thing. I feel like there should be a better time complexity option for this but honestly I can't think of one.

[@awekeningbro1207]

we can create a data structure that will contains 2d array like this: [ [h,d,l,c], [o], [t,g] ] each row index would correspond to the current index of the word and the letters inside each list can be iterated to check and swap to create a word if it exists in the dictionary.

[@davemustainejigsaw]

I can understand that this would help in finding if there's a possible way to get to the end word from the beginning word. But I'm not sure how it gives the shortest transformation? p.s: the intro --> 🔥

[@davemustainejigsaw]

Oh, my bad i guess it' coz, you'd be at the same level with the sibling nodes... I see. Sorry about that!

[@mridulchaudhary8545]

This questions has been labelled "Hard" now

[@nickv8707]

Only reason to copy data to Set was to use contains and remove methods in O(1) time

[@secularph8424]

Python strings are too immutable

[@beautifulmind684]

Hi, thx for your explanation, I'm wondering what recorder you were using in this video? looks like you got extra camera....

[@MohitSinha4]

Thats a very nice explanation, thanks!

[@obidulislam1657]

I am not sure how your code got accepted when the character replacement loop at line 22 doesn't include char 'z'. It should be

[@uwontlikeit]

Does it even work? This way of Level counting in BFS does not make any sense to me

[@boredasever6645]

Not going to lie, idk if this solution would be good enough for an interview. This runtime is really really bad.

[@bronsonschnitzel7493]

this is fine for interviews...

[@artofwrick]

It is bfs. There's nothing to shy about time complexity. It's all the same and everybody knows that

[@pratheek5096]

Could have just called a different function to check if the curr_word differs from the word being evaluated by one character or more

[@jayeshpokharkar2708]

Why do we need set.remove(new_word); ? There will not be duplicates as the character loop is going from a to z.

[@imkrrishnayak]

great explanation! keep up the good work!

[@pratheek5096]

They have mentioned to assume no duplicates...set is unnecessary right? Since List supports .contains() and .remove() methods ?

[@za3931]

contains and remove take O(n) so set is necessary af.

[@TeluguUSDiaries]

WordLadder II, please?

[@gloriasingh8516]

what is the Time complexity here? Can anyone tell?

[@sparkle3024]

the intro gave me a heart attack

[@arbazshaikh4447]

Hey good explanation! what is the time & space complexity ?

[@mrprime557]

O(M^2*N) where M is the length of the word and N is number of words.

[@akil1991gen]

it should be c

[@kavyatsaliki4642]

Please do word ladder ii @nickwhite

[@kamalpreetsingh4782]

Best intro😂😂

[@ahnaf77khan11]

The intro is cringy. But as always his contents are the best.

[@df5649]

how about ["a","b","c"]. Should be 2 levels,but turns to one if a transforms to c

[@pujamishra1475]

I'm struggling to understand why I get "Wrong Answer" when I use queue.size() in the for loop constraint and not use a size variable to assign the queue size before and then run for loop size times. Code shown below: //loop through the queue until empty while(!queue.isEmpty()){ for(int i = 0; i < queue.size(); i++){ // Here if I assign int size = queue.size() before for loop I get the correct answer. String curr_word = queue.poll(); //// Thanks in advance.

[@bronsonschnitzel7493]

queue is changing in size with every step of that iteration. Every time queue.poll() is called, queue.size() will change. you need to assign the size to a variable to retain the BFS level size.

[@pujamishra1475]

@@bronsonschnitzel7493 Thanks a lot for your reply. This really cleared the confusion I had.

[@f3-faithfitnessfinance]

Definitely first!

[@PedroTechnologies]

Bruh cant believe I found you here lmaooo

[@f3-faithfitnessfinance]

@@PedroTechnologies Hahaha😂😂😂 I am everywhere lol You have any interviews soon?

[@PedroTechnologies]

@@f3-faithfitnessfinance Have an interview next week for an internship. Might make a video about it if I get the offer!

[@f3-faithfitnessfinance]

@@PedroTechnologies Woohoo All the best bro🙌👍 Kill it🔥

[@haojia6308]

Hi Nick, I can do it by iteration but I am struggling why I cant do it in recursion. Any idea how to do it in recursion?

[@kushagrakulshrestha2966]

WTF DUDE lol ... never seen you give intro like this :D

[@lifehacks9450]

Pls upload questions on Prim's and kruskal algo

[@deeproy7292]

poll and offer...and loved the solution

[@Marina_DU]

Aquí está la fiesta 🥳🎊🎉

[@alvxlopez]

Thank you!

[@Haylem]

did not expect you to say N-Word. WOW

[@mukundsridhar4250]

you do a great impression of someone who is high

[@abdusalam3ar]

I thought you were high at first hahaha

[@rachitagrawal3570]

Coding problems and interview are literally broken sometimes. 😢

[@ankursuri3853]

You are the best!

[@TravelwithPanchi]

What is the time complexity?

[@meetnikhil719]

What would the time complexity be for this?

[@AmolGautam]

Thank you so much

[@NikhilVerma-kc3io]

what would be the time complexity of the above solutions?

[@mtvmango5172]

Is worst case time complexity for this solution M+26*n*M?

[@mdzikrullah9575]

nice explanation

[@iamabean]

is it similar to edit distance problem in Dynamic programming

[@koga7349]

Looping through the alphabet is not necessary and doesn't scale. What if the word is 5 letters long? You're brute forcing every possible 5 letter word. The runtime would be 26^5 or 11,881,376 iterations. Not to mention that we are already nested in multiple other loops. Instead just compare letter differences between your current word and dictionary words. If only one letter is different then the path is valid

[@mnchester]

great video!

[@shubhamnaik1982]

what was that in the initial , too funny

[@dipteshsil9299]

What is the time complexity of this code?

[@ashishbarai1425]

Best in you tube 👍

[@conf49]

What would be the time Complexity here?

[@artofwrick]

Medium?? Where are you?

[@ousmand742]

why did he remove the word on line 29 from the set

[@v.smourya8005]

it's like marking visited what we already explored so that we don't move backward in our search. hit --> hot if you don't remove the word "hit" from the set, you would revisit "hit" again when exploring "hot". what you don't want : hit --> hot --> hit --> hot --> hit --> hot ...

[@anneheaven0123]

I tried the same solution on Leetcode and the output is wrong. Could someone please tell me what I did wrong? Did I miss something or did the problem statement change? :'( class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { HashSet set=new HashSet(); for(String s: wordList) { set.add(s); System.out.print(s); } if(!set.contains(endWord)) return 0; Queue q=new LinkedList(); q.offer(beginWord); int level=1; while(!q.isEmpty()) { int size=q.size(); for(int i=0;i

[@HiBMlive]

you have written return level++; whereas it should be level++ only

[@anneheaven0123]

@@HiBMlive shows "Output limit exceeded" for input "zings" "brown"

[@HiBMlive]

@@anneheaven0123 remove the System.out.println lines and it should work

[@anneheaven0123]

@@HiBMlive That helped. Thank you!

[@chodingninjas7415]

great.

[@chanduc2000]

nice, it's Ok

[@baibhavghimire3827]

First for loop seems unnecessary.

[@monkyyy0]

>never again Please again

[@__nitinkumar__]

That intro 🤣🤣

[@lemp9582]

Nick did you find a job?

[@zyjian1921]

this is hard for sure.

[@unknownman1]

it is not in hard :)

[@emp_333]

Should be a hard really.

[@treeduck999]

That loop trough the alphabet is atrocious

[@AlexandrBorschchev]

Code is not as helpful as explaining it. Please sketch your thoughts as that would be more intuitive.