Word Ladder | Leetcode #127

This is a very famous and important problem in graph algorithm which is the word ladder problem and it is from leetcode #127.This problem is a tricky graph problem which can be solved using a set, queue and using BFS algorithm.DFS can't be used for this problem because that can have exponential number unique paths in a graph.We can use either DFS or BFS to find shortest path in Tree but we need to use BFS for finding shortest path in graph due to polynomial time of BFS.I have first explained the problem statement with all the constraints and then I have shown the observations and intuition for solving this problem.After this, I have shown the dry run using SET and BFS algorithm using queue.At the end of the video, I have also shown the code walk through for the solution.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

========================================================================
Join this channel to get access to perks:

=======================================================================

USEFUL LINKS:-

#graph #graphalgo #leetcode

[chiragmali]

Very well explained. but there is one issue in 2 min 12 sec the path of length 7 is wrong. you have changed two chars instead of 1, while transforming "lot" to "dog".

[shubhamkhurana]

Hey Man, I got placed today at Western Digital Corporation. Thanks a lot for your videos. Keep going🔥🔥

[leowu]

this is gold, especially for the ones who have questions on when should we use DFS and when we should use BFS

[kms]

Hello sir, I got placed at LinkedIn, thank you for your videos and constant guidance!!!.

[roshanraut]

Simply Makkhaan(Butter). What an amazing Hat's Off.

[otifelix]

your explanations are so good that i just listen to them and go ahead and solve the problem

[pratapkumarchandra]

Great explanation..Really enthralled by the way of explaining every bit

[mikec]

you really draw out all the words such an eyesoar man

[KarthikKumaresan-ko]

legendary explanation! Good job buddy!

[daanishsarguru]

Thanks you very much, I only needed the graph hint to solve this

[upendraroul]

Your explanation is to the point. Keep it up!

[theghostwhowalk]

Like before video as I know this will be awesome 😀 BFS approach I guess? Where at each step check new word can be formed with char. Replacement from A to Z...
For better time complexity, put all words in set.

[kathirraja]

Instead generating new string and find in in set we could compare two words

def is_one_word_change(w1, w2):
if len(w1)!=len(w2):
return False
wc = 0
for i in range(len(w1)):
if w1[i]!=w2[i]: wc+=1
if wc>1: return False
return wc==1
this will reduce the time

[rvrishav]

Can't we use dfs & dp to reduce complexity?

[amitavamozumder]

basically, we're assuming all edges are weight 1 and doing a djikstra.

[parteeksatija]

sir for checking string we are using set which gives us the result in average O(1) time then why have you written there that for string compare it is O(N*26*N) it should'nt be O(N*26) at 15:39?

[fadi.casual]

What tools do you use to draw on the screen? @TechDose?

[nitishgoyal]

Pls, discuss the 2-way Bfs approach also for this qs.

[utsavgupta]

If we check popped string with the end word at the starting only not in the for loop then tym complexity will we O(n*26*w)? Am i right?

[birajparikh]

Hello Tech Dose,
Amazing and detailed explanation.
What will be the space complexity?