Word Ladder 2 | Leetcode

แชร์
ฝัง
  • เผยแพร่เมื่อ 30 ม.ค. 2025

ความคิดเห็น • 92

  • @RahulVerma-fz2jf
    @RahulVerma-fz2jf 4 ปีที่แล้ว +29

    Really good. After going to 10 editorials, I finally understood Word Ladder 2 using this video. I am sure, I won't be forgetting it next time. Keep up the good work. :)

  • @shivanshrawat2688
    @shivanshrawat2688 4 ปีที่แล้ว +3

    I was just going to post a comment to ask you to put out a video for this problem. there is simply no good explanation for this one, and I was constantly checking your page if you have uploaded solution to word ladder 2 because i knew that i would only understand it over here. Many thanks and more thanks. This page is absolutely brilliant.

  • @JCatharsis
    @JCatharsis 3 ปีที่แล้ว +3

    Your approach seems the most intuitive and easy to understand compared to all leetcode solutions.. cheers mate

  • @babulbhanu8213
    @babulbhanu8213 4 ปีที่แล้ว +17

    Teaching is an art and you have mastered it . Thank you so much :)

  • @sthirumalai
    @sthirumalai 4 ปีที่แล้ว +5

    Hi, Your thought process is crystal clear. I implemented the solution using two BFS iterations instead of a BFS+DFS. But the intuition is the same. Great content. Thanks

  • @avinandanbanerjee9568
    @avinandanbanerjee9568 4 ปีที่แล้ว +6

    Thanks for the clear explanation! I wasn't able to get the special adjacency list, and leetcode solutions were very cryptic.

  • @tapeshmittal3287
    @tapeshmittal3287 3 ปีที่แล้ว +1

    Super video! I applauded for $2.00 👏

    • @techdose4u
      @techdose4u  3 ปีที่แล้ว

      Thanks for your support ❤️

  • @yitingg7942
    @yitingg7942 4 ปีที่แล้ว +2

    lol at the first second when I saw the graph you drew, I knew how to solve it. Thank you for being so inspiring Sir!

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

      😂 shit. You dint watch the video 🤣

    • @yitingg7942
      @yitingg7942 4 ปีที่แล้ว +1

      @@techdose4u hahahaha you caught me Sir!
      I actually still did Sir. I am half way now, trying to write the code while watching the video.

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว

      Nice 😊 All the best 👍🏼

    • @yitingg7942
      @yitingg7942 4 ปีที่แล้ว +1

      @@techdose4u Sir I was so naive, I thought I knew the answer so I skipped the second part. Then it took me hours struggling without getting the code right. Today I came back and saw the second part, only to find that I am a complete idiot by skipping it. Since you made everything crystal clear. If I have followed your process, I wouldn't struggle for that long.
      Thank you so much Sir. I appreciate everyday that you are here!!!!!!!

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

      Atleast you tried on your own. I am pleased to see that ❣️

  • @madmax2442
    @madmax2442 3 ปีที่แล้ว +5

    This was a tough one and still you made so clear! Hats off 🎩

  • @shivambharti8278
    @shivambharti8278 2 ปีที่แล้ว +15

    Giving TLE as of now. 32/35 test case passed :)

    • @tanmoypaul4268
      @tanmoypaul4268 2 ปีที่แล้ว

      Have u figured out why its giving tle?

  • @aushoroup2992
    @aushoroup2992 3 ปีที่แล้ว

    "Special Adjacency List" is the key. I got TLE while using the Normal Adjacency list. Thanks for helping me out.

    • @srishtijaiswal7079
      @srishtijaiswal7079 2 ปีที่แล้ว

      No tle if you use a visited hashmap parallel

  • @learn5371
    @learn5371 2 ปีที่แล้ว

    People like you make India proud

  • @MrJoyRana
    @MrJoyRana 8 หลายเดือนก่อน

    Great man!! I really struggled to understand and found this one, I was assured it's techdose :)

  • @code_life4835
    @code_life4835 4 ปีที่แล้ว +1

    Great Explanation Sir!
    Congrats for 30K Subscribers!

  • @1tav0
    @1tav0 2 ปีที่แล้ว

    Thank you so much for this explanantion this problem is not easy at all and ive learned it with this video. thank you so much

  • @andreafabris893
    @andreafabris893 3 ปีที่แล้ว +6

    Could you explain why the time Complexity of DFS is V*E in this case and not V+E? Thank you

  • @lisaren6661
    @lisaren6661 2 ปีที่แล้ว +1

    Wow! This is super clear. Thanks you so much!

  • @_inspireverse___
    @_inspireverse___ 2 ปีที่แล้ว +1

    Awesome! You made it so easy and clear ❤❤

  • @vishalmishra9549
    @vishalmishra9549 3 ปีที่แล้ว +1

    Thank you for this great solution. Learned new thing.

  • @rosail21
    @rosail21 4 ปีที่แล้ว +1

    Excellent Solution....Love your detailed analysis....Very unique an Enjoyable!

  • @nikhilpawariaaa
    @nikhilpawariaaa 2 ปีที่แล้ว

    THIS HELPED ME A LOT! THANKS

  • @dhanashreegodase4445
    @dhanashreegodase4445 2 ปีที่แล้ว +2

    gonna sleep for straight 2 hours after this question

  • @harshitpandey7521
    @harshitpandey7521 3 ปีที่แล้ว +5

    Why is the complexity of DFS traversal O(VE), shouldn't it be O(V+E)?

    • @tanujgupta143
      @tanujgupta143 3 ปีที่แล้ว

      it is not a simple DFS call. Simple traversing nodes using DFS gives O(V+E). This DFS prints all possible paths. Hence its worst time can be O(VE), best case can be O(V+E)

  • @rahulchudasama9363
    @rahulchudasama9363 4 ปีที่แล้ว +2

    Through this video, I realized what u think u can do it in code.
    Many times I feel whatever I am thinking as a solution is lengthy and it will be hard to debug and what if it will not work with hidden/many test cases?
    Thanks, TechDose :)

  • @abhishekbarman1837
    @abhishekbarman1837 4 ปีที่แล้ว +3

    I tried the code but instead of "dict.count" i used "dict.find" it gave TLE can u explain why ? and same for visited

  • @chris.w391
    @chris.w391 3 ปีที่แล้ว +1

    18:16 DFS in adjacency list should take O(V+E), right?

  • @Phoenix-xi2gy
    @Phoenix-xi2gy 3 ปีที่แล้ว +1

    Can u pls explain how the time Complexity of DFS will be V*E in this case? BTW love your videos.. Keep doing the good work!

  • @KM_1947
    @KM_1947 3 ปีที่แล้ว

    Really good explanation. Can you clarify why BFS alone would not suffice. While calculating minimum depth itself can't we maintain the path from startWord to the current node as an attribute of that node and return that attribuite when we reach endWord.

  • @secondIncomePartTime
    @secondIncomePartTime 2 ปีที่แล้ว

    bhad faad diya bhai

  • @satyanarayanagokavarapu3011
    @satyanarayanagokavarapu3011 4 ปีที่แล้ว +1

    Can you explain Guess the word problem ? That would be helpful

  • @PraddyumnShukla
    @PraddyumnShukla 2 ปีที่แล้ว +3

    This solution gives TLE

  • @LeoLeo-nx5gi
    @LeoLeo-nx5gi 4 ปีที่แล้ว +1

    Sir pls if u start DP pls do good hard level problems bcoz whether any one says or not one can find the easy level and most famous dp problems everywhere so that would really be waste of time to go on with the usual ones like LCS and so on.... I hope u understand Sir, sorry if I said something wrong but I wanted to say it before u were about to start🙏

    • @techdose4u
      @techdose4u  4 ปีที่แล้ว +1

      I will do problems of different types. All questions can't be very hard else very few will understand. I will do mix of problems.

  • @vinayakgandhi5690
    @vinayakgandhi5690 2 ปีที่แล้ว

    Instead of using the special adjacency list, can we just create a normal adjacency list like an undirected graph and keep a dfs visited array to make sure we don't visit any node again in one dfs path, but can visit it in some other dfs path?

  • @sushantkumar9711
    @sushantkumar9711 2 ปีที่แล้ว

    I think if we are facing difficulty understanding the special adjacency matrix. we can create a normal adjacency matrix and check if the current level is equal to the min level which we get from the BFS part and the current string is equal to the end word. if this is the case add else not. any views on this?

  • @Donutshop2365
    @Donutshop2365 3 ปีที่แล้ว +3

    Really good intuitive approach, but would TLE.

    • @techdose4u
      @techdose4u  3 ปีที่แล้ว

      :O

    • @uditagrawal6603
      @uditagrawal6603 3 ปีที่แล้ว

      @@techdose4u Initially was getting TLE but after optimisation with adjacency list it worked out.
      Nice approach!!!

  • @dataman4503
    @dataman4503 3 ปีที่แล้ว +2

    This problem is a bit hard. To solve this problem we need to use many DS (maps, queues, vectors,... ) . Lol.. I think if such questions are asked in Inteviews there is possibility that 1 hour will be consumed by this 1 problem alone.

  • @MrNeo086
    @MrNeo086 3 ปีที่แล้ว +1

    Amazing!

  • @RajeshKumar-ts4fw
    @RajeshKumar-ts4fw 2 ปีที่แล้ว +1

    this solution gives tle now

  • @shoaibakhtarshaikh3840
    @shoaibakhtarshaikh3840 4 ปีที่แล้ว

    sir we should be able to traverse from both the sides ?what if we want to transform word log to hit in this case we will not be able to find the path

    • @benjaminross5615
      @benjaminross5615 4 ปีที่แล้ว

      The structure of the DAG that is generated using this modified bfs algorithm is dependent on the start word and stop word. If the start word is “log” and the stop word is “hit” the graph would look different.

  • @LegitGamer2345
    @LegitGamer2345 3 ปีที่แล้ว +3

    java version :
    class Solution {
    public List findLadders(String beginWord, String endWord, List wordList) {
    HashMap adj = new HashMap();
    HashSet dict = new HashSet(wordList);
    Queue Q = new ArrayDeque();
    Q.add(beginWord);
    HashMap visited = new HashMap();
    visited.put(beginWord,0);
    while(Q.size()>0){
    String curr = Q.remove();
    for(int i =0;i

  • @sauravawesome
    @sauravawesome 3 ปีที่แล้ว +1

    if I use vis[temp] == 0 instead of vis.count(temp)==0 ,it gives runtime error can't see how or why ,can you please make this clear

    • @madmax2442
      @madmax2442 3 ปีที่แล้ว

      Because vis[temp] = 0 means that you have you have visited 'temp' and its level is zero (and in actuality, temp is still unvisited) and so you will not include it in your path.
      We have to include the ones who are not visited.. So, either use "vis.count(temp) == 0" or "vis.find(temp) == vis.end()" to apply the correct logic.

    • @shiqilyu6692
      @shiqilyu6692 2 ปีที่แล้ว

      same problem.

  • @nikhilmehta7298
    @nikhilmehta7298 2 ปีที่แล้ว

    It will return empty matrix after executing same code please help me in that

  • @PriyanshuKumar-ho7kj
    @PriyanshuKumar-ho7kj 2 ปีที่แล้ว

    Gives TLE now...although good approach

  • @amitupadhyay6511
    @amitupadhyay6511 2 ปีที่แล้ว +2

    It gives TLE in python

    • @danlan4132
      @danlan4132 2 ปีที่แล้ว +2

      same for c++ as well

  • @gomzysharma
    @gomzysharma 2 ปีที่แล้ว +1

    Getting TLE with this code+approach. Anyone else?

  • @rupalimaheshwari3024
    @rupalimaheshwari3024 2 ปีที่แล้ว

    26^N?

  • @yogeshsikanderpuriya7417
    @yogeshsikanderpuriya7417 2 ปีที่แล้ว

    getting tle now

    • @juzarantri864
      @juzarantri864 2 ปีที่แล้ว +1

      did u solved bro??

    • @player-te8tf
      @player-te8tf 2 ปีที่แล้ว +1

      @@juzarantri864 Yea

    • @juzarantri864
      @juzarantri864 2 ปีที่แล้ว +1

      @@player-te8tf please tell me from where did u find the approach and how u did it?

    • @player-te8tf
      @player-te8tf 2 ปีที่แล้ว +1

      @@juzarantri864 man i mean i solved it with the approch explained in the video, but it gave TLE.
      and this s*it requires higher brain functionality which i lack now... So i have added it in my to do list and will look into this q after i complete graph

    • @player-te8tf
      @player-te8tf 2 ปีที่แล้ว +1

      And yea... If u really wanna solve it then go to the leetcode discussion >

  • @anujtyagi4047
    @anujtyagi4047 2 ปีที่แล้ว +2

    your code giving tle

  • @UTTAMKUMAR-wd4zz
    @UTTAMKUMAR-wd4zz 2 ปีที่แล้ว +1

    TLE aara bae.

  • @ghazanferwahab5673
    @ghazanferwahab5673 3 ปีที่แล้ว

    plz give coe in java

  • @CareerHunt
    @CareerHunt 2 ปีที่แล้ว +2

    //100% pass test cases
    class Solution {
    public:
    void findAllPath(vector &res, string currentWord, string beginWord, unordered_map &parents, vector path) {
    if(currentWord == beginWord) {
    path.push_back(beginWord);
    reverse(path.begin(), path.end());
    res.push_back(path);
    return;
    }
    for(auto word: parents[currentWord]) {
    path.push_back(currentWord);
    findAllPath(res, word, beginWord, parents, path);
    path.pop_back();
    }
    }

    vector findLadders(string beginWord, string endWord, vector& wordList) {
    unordered_map wordMap;
    unordered_map parents;
    unordered_map levels;
    for(auto word: wordList) {
    wordMap[word] = true;
    }
    queue q;
    q.push(beginWord);
    int level = 0;
    levels[beginWord] = 0;
    while(!q.empty()) {
    string s = q.front();
    q.pop();
    for(int i=0; i

    • @tausifnawaz8187
      @tausifnawaz8187 2 ปีที่แล้ว +1

      can you please explain the problem in the original code and what changes you made to make the code work, I'm struggling to come to a conclusion???

    • @CareerHunt
      @CareerHunt 2 ปีที่แล้ว

      @@tausifnawaz8187 from this method, we are coming from end to starting while calculating path

    • @CareerHunt
      @CareerHunt 2 ปีที่แล้ว

      @@tausifnawaz8187 in the above video code, time limit happening due to multiple DFS on neighbours while calculating path.
      Suppose our level is more than 1+ level of curr. Then, We were not doing anything with those neighbours. But it should not be like that.
      So, in this approach we are trying to remove those neighbours whose level diff is more than one.

    • @nanotasza
      @nanotasza 10 หลายเดือนก่อน

      @@CareerHuntThis is genius, thanks!