Word Ladder | 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 ❤️

[@roshanraut3093]

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

[@techdose4u]

Thanks :)

[@otifelix]

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

[@techdose4u]

Nice :)

[@pratapkumarchandra6488]

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

[@techdose4u]

Thanks

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

👍

[@user-us7rg4cd6p]

legendary explanation! Good job buddy!

[@sangeetagautam733]

Thank you uncle ☺️❣️

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

[@mikec9444]

you really draw out all the words such an eyesoar man

[@techdose4u]

😅

[@amitavamozumder73]

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

[@prakharagarwal6237]

in simple words BFS

[@daanishsarguru3044]

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

[@techdose4u]

Nice :)

[@akhilesh59]

Very Nice Explanation! Thank you.

[@techdose4u]

Welcome 🤗

[@vinayppandey4321]

Greatt explanation sir

[@birajparikh3367]

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

[@SuperWhatusername]

Superb Thank you so much

[@rajatgupta-ld1wg]

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

[@techdose4u]

😅

[@jayalakshmij7623]

You explained in an Excellent way

[@techdose4u]

Thanks

[@ramsaikoushikpolisetty6999]

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

[@upendraroul343]

Your explanation is to the point. Keep it up!

[@techdose4u]

Thanks

[@anilchaudhry804]

this question was asked to me at amazon..

[@techdose4u]

Nice :)

[@gauravagarwal8592]

amazing viedoe

[@techdose4u]

Thanks

[@indraneelsarkar3452]

Awesome explanation, thanks you so much :)

[@techdose4u]

Welcome :)

[@shivarammuthukumaraswamy7164]

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

[@CodeSuccessChronicle]

Fabulous! Very clear

[@techdose4u]

Thanks 😊

[@nitishgoyal9910]

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

[@techdose4u]

Sure I will try

[@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 :)

[@lambar0]

Nice

[@techdose4u]

Thanks

[@surajmaity6194]

Very well explained.

[@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)?

[@madanmohanpachouly6135]

Well explained, thanks

[@coder1015]

I wish you are my csc sir

[@techdose4u]

🤗

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

[@alpishjain1317]

excellent dry run!

[@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 :)

[@onkarbagal8268]

Nice explanation 👍

[@techdose4u]

Thanks

[@ayushikumar34]

Thanks, it was amazing.

[@techdose4u]

Welcome :)

[@HimanshuSingh-ob9qo]

Nice explanation

[@techdose4u]

Thanks

[@BaljeetSingh-bx8yj]

Sirji pranaam 🙏🏻

[@techdose4u]

🙏

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

[@Mandeepsingh-jo5cf]

Thank you sir.

[@techdose4u]

Welcome :)

[@niharikagrover3523]

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

[@techdose4u]

Already done.

[@azeezsayyad7281]

U are great man

[@techdose4u]

Thanks

[@vickysingh1320]

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

[@techdose4u]

Sure bro. But Currently I am covering graph :)

[@willturner3440]

Great content 🔥🔥

[@techdose4u]

Thanks

[@Dan-tg3gs]

i was able to do this using BFS bidrectional

[@techdose4u]

Great ❤️

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

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

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

[@fadi.casual3796]

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

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

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

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

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

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

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

[@F21SafiyyaIshaqSyed]

was asked in phone pe

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

[@satyanarayanagokavarapu3011]

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

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

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

👍

[@TomJerry-bp9ig]

❤

[@007-yashchoudhery4]

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

[@abhilashpatel3036]

What's lsize doing? Please someone explain

[@swatygupta3753]

code link is broken, can you fix it.

[@techdose4u]

I will check

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

[@kirtanprajapati8464]

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

[@designandcraft]

😀

[@techdose4u]

😁

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

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@sharaddabhi493]

What will be the complixity of this code?

[@HimanshuSingh-ob9qo]

🙏

[@techdose4u]

🙏

[@HimanshuKumar-xz5tk]

What is the space complexity?

[@barshapaul9461]

are we using 0(zero) as true here?

[@SHASHIKUMAR-pp4hg]

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

[@21RandomMan]

uhh u can use bfs...

[@manasvinsharma1740]

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

[@sakshisinha8164]

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

[@arpanjena4595]

Is this code is in java or c++ ?

[@techdose4u]

Cpp

[@Sandeep-zd6dq]

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

[@SHASHANKRUSTAGII]

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

[@coder5518]

could u please send that solution link?

[@deathtrick]

Github not found

[@techdose4u]

It should work now. Try it.

[@worldofafrontenddeveloper9187]

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

[@mtvmango5172]

Dond dell me whad do do

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

👍🏼

[@jatinvishwakarma5272]

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

[@techdose4u]

Which question ?

[@rishabhkumar8115]

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

[@rishabhkumar8115]

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

[@techdose4u]

Thanks 😊

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