Word Ladder | Leetcode

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:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
BFS: • Breadth first search |...
Why DFS can't be used: codeforces.com/blog/entry/16479
#graph #graphalgo #leetcode

[@chiragmali6752]

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".

[@techdose4u]

Yea. I did that in graph and I have flagged a correction there.

[@chiragmali6752]

@@techdose4u Cool.. keep it up!!

[@techdose4u]

@@chiragmali6752 thanks :)

[@shubhamkhurana7545]

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

[@techdose4u]

Woww great 🎉 Congratulations 💥 Would love to hear from you in LinkedIn. Please ping there.

[@raviashwin1157]

how did you apply for the company,it was on campus or off campus??

[@leowu5058]

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

[@kms8320]

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

[@techdose4u]

Great ❤️

[@rishabhkumar8115]

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

[@shivarammuthukumaraswamy7164]

Thank you so very much.Best explanation for this problem.

[@otifelix]

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

[@techdose4u]

Nice :)

[@user-us7rg4cd6p]

legendary explanation! Good job buddy!

[@user-sr1pk3yy8b]

Hi, thanks for the problem explanation. Question: why don't we put "wordList" to a Dictionary instead of Set so to make word comparison O(1)?

[@roshanraut3093]

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

[@techdose4u]

Thanks :)

[@fadi.casual3796]

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

[@daanishsarguru3044]

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

[@techdose4u]

Nice :)

[@alpishjain1317]

excellent dry run!

[@sangeetagautam733]

Thank you uncle ☺️❣️

[@upendraroul343]

Your explanation is to the point. Keep it up!

[@techdose4u]

Thanks

[@utsavgupta746]

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?

[@SuperWhatusername]

Superb Thank you so much

[@indraneelsarkar3452]

Awesome explanation, thanks you so much :)

[@techdose4u]

Welcome :)

[@birajparikh3367]

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

[@akhilesh59]

Very Nice Explanation! Thank you.

[@techdose4u]

Welcome 🤗

[@surajmaity6194]

Very well explained.

[@vinayppandey4321]

Greatt explanation sir

[@madanmohanpachouly6135]

Well explained, thanks

[@mikec9444]

you really draw out all the words such an eyesoar man

[@techdose4u]

😅

[@kathirraja4709]

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

[@techdose4u]

👍

[@jayalakshmij7623]

You explained in an Excellent way

[@techdose4u]

Thanks

[@CodeSuccessChronicle]

Fabulous! Very clear

[@techdose4u]

Thanks 😊

[@ramsaikoushikpolisetty6999]

Well explained, but if you use set(for find()) then I feel complexity will be O(N2.WLogW).

[@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.

[@techdose4u]

Yep. You already solved it :D

[@ayushthakur2896]

why using set gives better complexity?

[@LGL1999]

@@ayushthakur2896 Constant time access to elements in Sets vs Lists I think?

[@ayushikumar34]

Thanks, it was amazing.

[@techdose4u]

Welcome :)

[@amitavamozumder73]

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

[@prakharagarwal6237]

in simple words BFS

[@allen724]

Can someone please explain why DFS doesnt work? I tried implementing with DFS and using a HashMap to store computed results already. But I am getting the wrong answer, getting 41/49 on leetcode.

[@rvrishav7]

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

[@hangto0401]

could anybody please tell me that why DFS does not work in this problem? Need help thank you~

[@BaljeetSingh-bx8yj]

Sirji pranaam 🙏🏻

[@techdose4u]

🙏

[@rajatgupta-ld1wg]

Just Curious, why you disliked this ques? at 0:08 :P btw I always find your videos easy to understand. Thanks :)

[@techdose4u]

😅

[@willturner3440]

Great content 🔥🔥

[@techdose4u]

Thanks

[@Mandeepsingh-jo5cf]

Thank you sir.

[@techdose4u]

Welcome :)

[@anilchaudhry804]

this question was asked to me at amazon..

[@techdose4u]

Nice :)

[@onkarbagal8268]

Nice explanation 👍

[@techdose4u]

Thanks

[@azeezsayyad7281]

U are great man

[@techdose4u]

Thanks

[@saunaknandi1814]

Sir in graph we used visited matrix then why not here. The remove method here will charge O(n) thereby increasing the time complexity

[@nitishgoyal9910]

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

[@techdose4u]

Sure I will try

[@gauravagarwal8592]

amazing viedoe

[@techdose4u]

Thanks

[@abhilashpatel3036]

What's lsize doing? Please someone explain

[@HimanshuSingh-ob9qo]

Nice explanation

[@techdose4u]

Thanks

[@niharikagrover3523]

Hey, well explained. Can you do it for word ladder 2 problem also ?

[@techdose4u]

Already done.

[@abhireddy8164]

Thank you sir.very good explanation .please good the same one in graph too sir .it is very useful to know multiple approaches

[@techdose4u]

Welcome :)

[@kirtanprajapati8464]

hey bro apka brute force approch mind bloing he but kya iska optimal solution nhi he ?

[@pleasesirmorevideos4684]

so the main idea was to use O(n^2) to make the vali edges between words and then simply apply BFS?

[@parteeksatija5536]

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?

[@techdose4u]

26 permutation for each letter. For a word, you will have 26*N. You can have N words at a level. So a total of (26*N*N).

[@parteeksatija5536]

@@techdose4u Sir lets say there is a word "hit" now to try every combination time will be O(26*N) for one word and we can have total N words so time complexity would be O(26*N*N). Sir then What is W for in O(26*N*N*W)?

[@paraschawla3757]

@@parteeksatija5536
* TC O(26*N*N*W)
* N - Number of characters in String
* 26*N - Number of transformations happening in a string of N characters
* 26*N*N - Comparison with endWord string ( String comparison is O(N))
* W - Number of Words in the BFS call
Second multiplication by N is because all transformations i.e. 26*N occurrences of strings are being compared by endWord
String comparison is O(N) , check stackoverflow.com/questions/55330338/time-complexity-of-string-comparison/55330371
W - total number of words added in queue

[@siddharthsinghvi9972]

I think there will be an error we have to return 0 at the end as if the endword is also present but there is no path in the graph to end word so we will return 0 then

[@lambar0]

Nice

[@techdose4u]

Thanks

[@vickysingh1320]

Please make a video on the Manacher's Algorithm..

[@techdose4u]

Sure bro. But Currently I am covering graph :)

[@rohanseth1392]

I learn a lot from your videos.
Can you guide us of how you manage to stay dedicated for coding while being working in corporate ? I am working in corporate, I too want to go too far in coding, but not able to due.
Please guide us

[@techdose4u]

Sure

[@rohanseth1392]

I liked your planning videos very much. Can you make a video telling us about the plan for those who are working in corporate

[@HimanshuKumar-xz5tk]

What is the space complexity?

[@coder1015]

I wish you are my csc sir

[@techdose4u]

🤗

[@dhanashreegodase4445]

thank you so much..awesome..I am following your videos since 1 yr. I can't find your coding profiles anywhere.(want to see)😁

[@techdose4u]

Thanks :)

[@barshapaul9461]

are we using 0(zero) as true here?

[@sharaddabhi493]

What will be the complixity of this code?

[@TomJerry-bp9ig]

❤

[@nikhilchandna4851]

Why didn't you consider find and erase function time complexity in the Final Time complexity??
Btw great explanation

[@techdose4u]

Maybe I missed 😅 It's easy to miss something when calculating time complexity.

[@namithas6546]

Hi, I just had a doubt regarding the following test case.
beginWord = "a"
endWord = "c"
wordList = ["a","b","c"]
can anyone clarify why its output is 2 and not 1?

[@lokeshkoliparthi9268]

we have to start counting from first node

[@devyeag3096]

First start "a" change to it a to z if it is present as a same then we ignored it( suppose after convert a to a then it is same then we ignore it then check for b to z and depth = 1) and check for other character and it is find then add it (convert a to c it is find then depth = 1+1) and returns it...

[@007-yashchoudhery4]

how you can make dog from lot? this connection is invalid.

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@HimanshuSingh-ob9qo]

🙏

[@techdose4u]

🙏

[@satyanarayanagokavarapu3011]

Design Search Autocomplete System can you make an video on this ?

[@raghugore3990]

Can u please provide solution and explanation for the below :
Write a program to find Largest 4 digits Prime Number whose Sum of Digits is also Prime.
1.Prime Number is any number that is divisible only by 1 and itself. Examples are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,........
2.Sum of Digits means sum of all the digits in that number. Example is number is 1234 then the sum of digits is 1+2+3+4=10

[@Dan-tg3gs]

i was able to do this using BFS bidrectional

[@techdose4u]

Great ❤️

[@rahulkhatoliya6814]

*** JAVA VERSION OF YOUR ALGORITHM ***
class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {

boolean isEndPresent=false;
Set St=new HashSet();

for(String s: wordList){

if(s.equals(endWord)){
isEndPresent=true;
}

St.add(s);
}

if(!isEndPresent) return 0;

int depth=0;
Queue Q=new LinkedList();
Q.offer(beginWord);

while(!Q.isEmpty()){

depth+=1;
int lSize=Q.size();

while(lSize-->0){

String curr=Q.poll();
int len=curr.length();

for(int i=0;i

[@designandcraft]

😀

[@techdose4u]

😁

[@swatygupta3753]

code link is broken, can you fix it.

[@techdose4u]

I will check

[@SHASHIKUMAR-pp4hg]

I tried using dfs+memorization but getting 44th testcase wrong anyone else

[@arpanjena4595]

Is this code is in java or c++ ?

[@techdose4u]

Cpp

[@yeswanthbonagiri7142]

I looking for bidirectional bfs approach in the video :(

[@techdose4u]

Don't worry. I will cover biderectional BFS in other questions. I thought it will be easier for most people to understand simple BFS. It will be helpful if you can recommend a most asked question in interview regarding birectional BFS :)

[@yeswanthbonagiri7142]

@@techdose4u I think a simple question is :
Given an undirected uniform graph, a source node and destination node, find minimum no of nodes exists in the path btw them.
This is similar to word ladder 😅 I guess.

[@techdose4u]

@@yeswanthbonagiri7142 Yea 😅 I needed a proper asked question.

[@yeswanthbonagiri7142]

@@techdose4u leetcode.com/problems/open-the-lock/
leetcode.com/problems/jump-game-iv/solution/

[@sakshisinha8164]

Why used set??????????

[@ravishasharma1219]

I think you don't need to do line 14 to 21 in the latest version of the question

[@techdose4u]

:o Dint check it

[@yatinarora1252]

I have tried this similar question from leetcode today...but the expected answer is 5 mine is 6.I was doing this some different algo..Bu I donot know that graph will be used in this question..Meaning this question is of graph

[@techdose4u]

👍

[@manasvinsharma1740]

Anyone noticed that TechDose has downvoted this question... 😂

[@anushkaagrawal1185]

I have a doubt. in the given example how u transformed lot to dog as it is given that only one letter transformation is valid.

[@techdose4u]

That was incorrect. I had flagged the correction when I was showing the graph. Dint realize it earlier in the previous slide.

[@21RandomMan]

uhh u can use bfs...

[@palakmantry]

You mentioned curr.compare(temp) is taking O(N) time complexity, why not just check `if curr==temp` this would be O(1)

[@manokumar89]

curr==temp is not O(1). its o(len of the string). its does a deep check.

[@Sandeep-zd6dq]

Leave everything else, At 0:17 you also disliked the problem 😂

[@deathtrick]

Github not found

[@techdose4u]

It should work now. Try it.

[@mtvmango5172]

Dond dell me whad do do

[@worldofafrontenddeveloper9187]

Thanks for the explanation.Just that too many ads , as I don't have premium.It is quite distracting.

[@SHASHANKRUSTAGII]

This is not the optimal way to solve this question. An nlogn solution exists

[@coder5518]

could u please send that solution link?

[@jatinvishwakarma5272]

Why there is so dislike on the question, even you also disliked it?

[@techdose4u]

Which question ?

[@jacobstech1777]

your code is not compact enough.

[@jacobstech1777]

# compact solution
wordList = set(wordList)
queue = collections.deque([[beginWord, 1]])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
wordList.remove(next_word)
queue.append([next_word, length + 1])
return 0

[@techdose4u]

👍🏼

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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