G-29. Word Ladder - I | Shortest Paths

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@ayushpatel2171]

Honestly I feel that the hard part about this question was figuring out that it is a graph question. But since I was following the playlist I already knew that it is a graph question. Which is why upon looking the question the intuition came easily to me.

[@ridj41]

naah since,src and dest pointers were there, it was easy to figure out it was a graph,but rest was difficult

[@sahilbani7020]

How is this even a Graph problem?

[@topgunn6683]

Watching your lectures before the Google on-site interview

[@harshdasila6680]

if you got selected refer me too :)

[@aryashjain7893]

linkedln id dedo bhaiya XD

[@gp7060]

I have my google on-site next month.. want to discuss on prep so can we connect on LinkedIn ?

[@shyren_more]

how did it go?

[@anonymousanonymous7507]

Ok Googler

[@vaarigupta6332]

Instead of erasing the string from the set, you can take unordered_map and mark it as true which is generally used in BFS for marking visited nodes.

[@infinityzero2321]

ya but that will unnecessarily increase the space complexity

[@jagannathan1014]

Terrible idea as it not only increases SC , but also increases COLLISIONS leading to worst case in hashmap

[@abhinavgupta7048]

@@jagannathan1014 can you please elaborate why it is a terrible idea and how will it increase collisions

[@priyanshkumar17]

yeah you can do it too...

[@Predator-pv7of]

@@abhinavgupta7048 it is generally advised to not use unordered sets and maps, and due to collisions, the worst case time complexity to access elements becomes O(n)

[@manasranjanmahapatra3729]

Understood. Graph is slightly tough, but you are making it easy for us thank you🤘.

[@prashantkashyap171]

For second time I was able to solve GFG hard problem on my own , such a nice teaching. Though I doubt if such approach would've hit, if it hadn't been a part of Graph series.

[@tanya8353]

The patience with which you do dry run is really commendable!!!!🔥

[@gorilla_coder-el6kf]

thank you striver i was able to solve this problem on my own because of your graph playlist. heartiful thanks for this playlist.this is the best out there.

[@arjunjadhav6275]

i just watched the logic you have used and i was able to write code by myself , Thanks..🙏

[@anshjain5673]

I solved this question in the following way which gives me the time complexity of O(n*m). I basically created the graph using adj list method and performed normal BFS instead of checking words in the set after modifying each letter of word. class Solution { public: bool checkDiff(string a, string b){ int ptr=0, count=0; while(ptr!=a.size()){ if(a[ptr]==b[ptr]){ ptr++; continue; } ptr++; count++; } return count==1; } int ladderLength(string beginWord, string endWord, vector& wordList) { wordList.insert(wordList.begin(), beginWord); int n = wordList.size(); vector adj[n]; //Create undirected graph for(int i=0; i

[@pramukhjain1742]

The graph creation will take time = (N^2)*M (where N is length of words array & M is length of longest word).

[@sam_55555]

Thank you so much Striver for explaining problems in a very understandable way. Kudos to you for achieving lot at a very young age in the world of Top-tech

[@manasvinsharma1740]

One more approach can be making the graph first & then finding the shortest path in it. We can make a graph where there will be a edge between all those nodes who differ by only 1 character. The graph creation will take time = (N^2)*M (where N is length of words array & M is length of longest word). Once graph is made we can apply BFS & also handle the case where target cannot reach.

[@abhisheksen7990]

I was thinking the same way

[@jyothiyadav2595]

i tried this but it says tle?? class Solution(object): def ladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int """ def issimilar(s1,s2): if len(s1)!=len(s2): return False l=len(s1) flag=True for i in range(l): if s1[i]!=s2[i] and flag==False: return False if s1[i]!=s2[i]: flag=False return True if endWord in wordList: final=wordList.index(endWord) que=[] n=len(wordList) adj=[[] for _ in range(n)] visited=[0 for _ in range(n)] for i in range(n-1): for j in range(1,n): if issimilar(wordList[i],wordList[j]): adj[i].append(j) adj[j].append(i) for i in range(n): if issimilar(wordList[i],beginWord): que.append((i,2)) visited[i]=1 while que: v,dis=que.pop(0) if v==final: return dis for i in adj[v]: if visited[i]==0: que.append((i,dis+1)) visited[i]=1 return 0 can someone help??

[@aruna5869]

Understood. You are brilliant in finding the suitable example to explain the algorithm....!! Thanks a lot🙌❤

[@harshvaghani4283]

You gave me the confidence of solving a leetcode hard! The step by step explanation is wonderful!!

[@santanu29]

I remember this problem came in Leetcode daily in Feb 2022. Just copied the code and did not understand anything. One year later I understood the code. Thank you for the explanation.

[@priyanshkumar17]

excellent memory brother

[@cinime]

Understood! What an excellent explanation as always, thank you very much!!

[@anandkalpe2155]

Hey @striver this solution is exceeding time limit in leetcode, so instead of assigning all letter from a-z , I tried with letters only in wordList and it worked. I just added below function to get all the letters into vector- private: vector letters(vector&wordList){ unordered_set st; vector result; for(auto it: wordList){ for(int i=0;i

[@subratkumar7359]

I wrote the same code and it didn't give TLE.

[@aryashjain7893]

Understood , a big fan of your zero typing errors !!!!! awesome video as always thank you sir ji

[@QuantaBytes]

Hey Striver !! Your Videos are reaallly really helpful, easy to understand, and hats off for your amazing work and efforts.

[@AyushMishra-b8w]

you can make any difficult question way too easy. Just loved your teaching style .😊😊😊😊

[@tanujaSangwan]

My approach is different: This can be visualised as an undirected weighted graph with unit weights. We can created graph with word as each node and all neighbours are the words with only one character changed. Then apply exact same BFS as we implement in the previous video. No code changes at all. Quite simple and passes all testcases. bool isAdjacent(const string& word1, const string& word2) { int diff = 0; for (int i = 0; i < word1.size(); ++i) { if (word1[i] != word2[i]) { diff++; if (diff > 1) return false; } } return diff == 1; } // Function to create the adjacency list graph unordered_map buildGraph(vector& wordList) { unordered_map graph; // Add an empty list for each word for (const string& word : wordList) { graph[word] = {}; } // Connect each word with its adjacent words for (int i = 0; i < wordList.size(); ++i) { for (int j = i + 1; j < wordList.size(); ++j) { if (isAdjacent(wordList[i], wordList[j])) { graph[wordList[i]].push_back(wordList[j]); graph[wordList[j]].push_back(wordList[i]); } } } return graph; } int wordLadderLength(string startWord, string targetWord, vector& wordList) { // If targetWord is not in the wordList, no valid transformation is possible if (find(wordList.begin(), wordList.end(), targetWord) == wordList.end()) { return 0; } // Include the startWord in the word list if it's not already there if (find(wordList.begin(), wordList.end(), startWord) == wordList.end()) { wordList.push_back(startWord); } // Build the graph from the word list unordered_map graph = buildGraph(wordList); // Perform BFS to find the shortest path unordered_map distance; for (const string& word : wordList) { distance[word] = INT_MAX; // Initialize distances with infinity } distance[startWord] = 1; queue q; q.push(startWord); while (!q.empty()) { string currentWord = q.front(); q.pop(); // Traverse all neighbors of the current word for (const string& neighbor : graph[currentWord]) { if (distance[neighbor] == INT_MAX) { // If not visited distance[neighbor] = distance[currentWord] + 1; q.push(neighbor); // If we reach the target word, return the distance if (neighbor == targetWord) { return distance[neighbor]; } } } } // If BFS completes without finding the targetWord, return 0 return 0; }

[@manjotsingh8157]

can u share the code?

[@divyareddy7622]

love it, just higher time complexity while building the graph--can go up to N^2

[@tanujaSangwan]

@@divyareddy7622 yeah

[@SumitKeshariMCS]

Bravo, amazing!! I was always afraid of this question. But you explained it sooooo well. Thanks a lot striver.

[@sypher4735]

Yeah, it came out to be very simple.

[@harishchoudhary9662]

It took me around one day to solve these question using my method but in the end it got TLE on leetcode and now after seeing the solution the questions seems easy.

[@rajatsaraf237]

Thanks striver, Was able to solve it by myself although my approach was different from this, I considered every node has a edge to every other node and each edge has a weight equal to the difference b/w the 2 vertices(words) Then just used the shortest distance for an undirected graph using BFS algo

[@arjunrai8126]

By node you mean the words right

[@rajatsaraf237]

@@arjunrai8126 yes

[@arjunrai8126]

@@rajatsaraf237 by difference bw the words you mean the number of positions where the chars are different , right? Great solution

[@rajatsaraf237]

@@arjunrai8126 yes, that char difference can be considered as the weight b/w two words

[@rishabhinc2936]

W bro

[@mahipatel9672]

Happy Teacher's day to you. You have helped so many of us to get their DSA concepts right. Kudos to you and thanks a lot :)

[@niteshbaith6350]

Your explanation is brilliant, bro!!

[@gugli28]

Simple bruteForce can be : for each element(say "hit") in list, compare it with the all other elements. If the only 1 char varies that we can add as part of adjacency List of "hit" and so on.

[@deepakagrawal7687]

we can create graph from the word list and do topological sort on it. that will give only limited characters that exists in word list and we can try out replacing characters present in word list only. with topological sort the we get array as h,d,l,c,o,t,g. Now I know before o I have 4 characters to try for first place i.e. h,d,l,c. then for g I have 2 characters o and t with same BFS algoritm we can avoid trying out all a-z combination and also it makes sense logically because after transformation if word should be from word list then try out with characters that are only in wordlist. if z is not present in wordlist in any word why to try out with that. Considering if there is no cycle in it. This needs to be asked to interviewer whether there will be cycle in the graph. If cycle exists then the other approach is to iterate through all the wordlist and put them in set. Atleast you will be comparing less characters then a-z

[@stith_pragya]

Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ITSuyashTiwari]

your explanation made it too easy🤗

[@mriduljain6809]

Was able to solve the problem on my own only because of you...Thank U😊😊 Understood Bhaiya..

[@_lifestylefusion]

Very clear explanation. Hats off to your effort .

[@yashveernathawat8154]

For string set.find() method takes O(N) instead of logn.... It increases the complexity

[@KratosProton]

Understood, quality content!

[@gutkaganggaming]

The other way we can do is Instead of making combination from current word Just check if we can make current word from any word present in the word list.

[@parallax8916]

Briliiantly explained When I read the question for the first time, I was so scared and I had no clue how to proceed. I was thing of sets and recursion but I did not even try coz Iwas scared. But u made it soo simple that after watching half of the video, I did it in 1 go . U r amazing striver. please continue to bring such playlists , its so helpful

[@priyanshkumar17]

were you thinking about backtracking too in first go?

[@studynewthings1727]

understood. Able to write the code by myself after getting the intuition.

[@psydook]

once i knew it was a graph question, i tried this myself : class Solution { private: bool check(const string& w1, const string& w2) { int differences = 0; for (int i = 0; i < w1.length(); ++i) { if (w1[i] != w2[i]) { differences++; if (differences > 1) return false; } } return true; } public: int ladderLength(string beginWord, string endWord, vector& wordList) { bool possible = false; int index = -1; for (int i = 0; i < wordList.size(); i++) { if (wordList[i] == endWord) { index = i; possible = true; break; } } if (!possible) return 0; wordList.insert(wordList.begin(), beginWord); int n = wordList.size(); vector adj(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (check(wordList[i], wordList[j])) { adj[i].push_back(j); adj[j].push_back(i); } } } vector distance(n, INT_MAX); queue q; q.push({0, 0}); distance[0] = 0; while (!q.empty()) { int node = q.front().first; int dist = q.front().second; q.pop(); for (int val : adj[node]) { if (distance[val] > dist + 1) { distance[val] = dist + 1; q.push({val, dist + 1}); } } } if (distance[index + 1] < INT_MAX) return distance[index + 1] + 1; return 0; } };

[@Sara-ed3jq]

Best series on graph

[@yasaswinikarumuri9590]

Such a great explanation! Please continue the playlist

[@Engineer_Padai]

thanks striver bhai, for this awesome series

[@senvikas1946]

I did like and kya hi samjhate ho yrr bhaiya, maza hi aa gaya. UNDERSTOOD

[@sukhpreetsingh5200]

excellent explanation as always, thank you very much!! Amazing playlist

[@kaichang8186]

understood, thanks for the detail explanation

[@priyanshkumar17]

One can figure out that it was a graph question by looking at src & dest strings, & shortest sequence of transformations were asked...So, some 'feeling' of shortest path from src (beginWord) to dest (endWord) comes...

[@gauravgupta7280]

A Small Optimization Can be MADE further ... So currently, for each index of the string we are traversing 26 times representing 26 characters / alphabets in the English Dictionary. But what if we exactly store the possible set of characters that are only available in wordList. There comes the optimization where we store set of all alphabets for each index & always iterate those in the while loop of queue.

[@charan775]

another approach is to use bi-directional BFS. same time complexity but half the runtime

[@empvaibhav9799]

Instead of converting str to all the possible strings we can simply compare str with all the strings in word_List and see if the difference btw them is 1 or less and if so then add in queue to do BFS.

[@harleenkaur7751]

Thanks a lot, Striver. Best explanation . 😀

[@vatsalvasoya5243]

Understood!! Very well explained!!!

[@Health_asset]

best method to solve this question 😁thanks striver I got your algo and tried myself , just make a little mistake but it was corrected bcoz of your code

[@user-rf3he9uv5m]

UNDERSTOOD striver!

[@techatnyc7320]

Great work, Raj!

[@pradhuman_ramawat]

I have a different solution, i created a graph representation using adjacency list (word is the key, words it can transform into are list values), then applied shortest distance method using dijkstra's algorithm.

[@AnushkaVijay-cv7tk]

can u please share your code....im having difficulty in making adjacency list

[@harshdiwase1941]

this question was amazing , thanks striver

[@breakthecode8323]

Striver, thank you so much for graph series, per please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na ek series please

[@disciplines4]

thanks striver for such wonderful explanation.

[@amanasrani6405]

yours HArdwork is really ❤

[@Amitkumar-nk5mo]

understood....your explainations are lucid ....keep up the good work...

[@mohammadkaif8143]

Hi, awesome video. Just add one base condition to handle this case, according to your code it will give 1 but it should return 0.. 1 der der der

[@rushikeshg25]

Thank you for such a wonderful Explanation !!!!

[@1tav0]

understood! amazing like always.

[@shreycpaunwala1420]

Hey Striver! Understood the concept thoroughly. Had one doubt, my first intuition was to use DP in this question instead of graph. SO why graph is more optimal then dp?

[@brokegod5871]

1) The question has a source to destination pattern, it's guiding you a path that you start from this word and end somewhere... This intends graph... Also they are saying "shortest" while giving you source and destination so you should think of shortest path algorithm 2) Reason why you thought of Recursion/DP is because we are trying every letter combination which is fair to think but you apply DP when you have a vast search space and you have no clue which can be the answer but here they've given you the dictionary list so they are telling you the search space

[@GM-rw5fl]

How u make the hard question like a cake work amazing brother ......

[@devangsingh2950]

One different approach is make a graph with edges between hit and hot, hot and dot, hot and dot, hot and lot, .... And now you have to find the shortest distance between two points (beginWord and endWord) using BFS.

[@priyanshkumar17]

Yeah

[@raghavmanish24]

thnaku striver ...you are making my carrir

[@rishavkumar2182]

great explanation!!

[@nagame859]

really don't understand why this is marked as "hard", this is one of the easiest problems, and it can also be considered as tree too.. regardless.. thank you Striver❤

[@pratikshadhole6694]

GOAT❤ you are great striver

[@sambhavagarwal5871]

Understood! What an excellent explanation as always, thank you very much!! Amazing playlist thanks striver is this playlist is completed or not please confirm

[@takeUforward]

It will have more videos.

[@sambhavagarwal5871]

Can u please upload fast

[@vikas7588]

It's a high time youtube should add a super like button.

[@aditikumari8204]

understood..thanks bhaiya

[@anchaldevrani2055]

Understood 🎉

[@ultimatecreed5144]

is use of unorderedmap better of unordered set and why??

[@_hulk748]

Understood sir thankyou sir❤🙏🙇‍♂️

[@sakethkumarpeddi2089]

Great explanation. But, can anyone confirm me that we can also get this problem done by using DFS right? By creating the adjacency list to backtrack again when particular node's dfs is over. I know this will take more time and space, but I want to know whether we can achieve this by doing DFS or not?

[@AyushSingh-fu1yp]

The hard part about the question is to figure out that it is a graph question, otherwise, doesn't have any substance.

[@a2_63_vimalmishra9]

At instead of set i have used map O(1) in every case : )

[@priyanshkumar17]

there can be collisions in a hashmap

[@DharnaMittal-vz9fi]

Striver you are the best

[@abhishek__anand__]

Nicely Explained

[@ayushmaanpandey5233]

one doubt : why don't we replace the char of the word string with the respective char withthe same index of string present in the set, not from the 26 alphabet???.it will save time if give wordlist length is less than 26 otherwise above code is okay

[@nirupamkumar6760]

very nice explanation

[@sherlockholmes1605]

Amazing explanation and logic! kuch bhi bolo, Striver bhai is built different!

[@lethalgaming7087]

Here is the Java Implementation: class Solution { static class Pair { String st; int step; Pair(String st, int pair) { this.st=st; this.step=pair; } } public int wordLadderLength(String startWord, String targetWord, String[] wordList) { Set set=new HashSet(); for(String s:wordList) set.add(s); set.remove(startWord); Deque q=new ArrayDeque(); q.add(new Pair(startWord,1)); while(!q.isEmpty()) { Pair p=q.pollFirst(); char[] word=p.st.toCharArray(); int step=p.step; if(p.st.equals(targetWord)) return step; for(int i=0;i

[@anshumansingh2715]

As mentioned in question "startWord may or may not be part of the wordList" but in code of C++ at line 13, you delete it every time without searching whether it is there or not, and still your code is running fine. can you pls state the reason for that? @striver

[@AB-yl5sz]

set.erase() function returns 1 if it deletes the element from set or return 0 if element doesn't present in set. So no error and code runs fine

[@LBK3]

understood ❤

[@GoodLuck-dv2zu]

As always AMAZING!

[@Siddhartha_Bose]

one of the toughest question in this playlist

[@jaishriharivishnu]

no, just because in starting he said tough, doesn't make it tough. Just usual BFS question.

[@KratosProton]

Great explaination

[@srujanveshkotha7286]

brute force approach using simple recursion: class Solution { public int wordLadderLength(String startWord, String targetWord, String[] wordList) { Set set = new HashSet(); for(String s : wordList) { set.add(s); } List stepList = new ArrayList(); wordLadderLength(startWord, targetWord, wordList,set,startWord,0,stepList); int ans=1000000000; for(int i=0;i

[@udaytewary3809]

Understood bhaiya

[@arjunbajpai3514]

If we have an unordered set of strings and suppose we have to search for a particular string in it what will the complexity be ... is it constant or order of string length? Kindly confirm.

[@UECAshutoshKumar]

Thank you sir

[@sumanthreddy7670]

can this be done using DFS approach instead of BFS?

[@AppaniMadhavi]

It means the brute is the optimised right??

[@2000UK-v8c]

Kudos to you sir!!

[@MMNayem-dq4kd]

Understood,sir.

[@akuma_168]

what if we first arrived at odisha by following the 2nd path instead of first?

[@DevashishJose]

understood, Thank you.

[@vijayanks1714]

Watching your lecture before the Meta phone screen round

[@Learnprogramming-q7f]

Thank you bhaiya