A 25-line 1204ms BFS solution


  • 8
    H

    The following is a BFS solution. Any suggestion for improvement of my code is welcome. Is there any other solution better than BFS?

    class Solution {
        public:
            int ladderLength(string start, string end, unordered_set<string> &dict) {
                unordered_map<string, int> dis; // store the distance from start to the current word
                queue<string> q; // FIFO for bfs purpose
                dis[start] = 1;
                q.push(start);
                while (!q.empty()) {
                    string word = q.front(); q.pop();
                    if (word == end) break;
                    for (int i = 0; i < word.size(); i++) {
                        for (int j = 0; j < 26; j++) {
                            string newWord = word;
                            newWord[i] = 'a' + j;
                            if (dict.count(newWord) > 0 && dis.count(newWord) == 0) {
                                dis[newWord] = dis[word] + 1;
                                q.push(newWord);
                            }
                        }
                    }
                }
                if (dis.count(end) == 0) return 0;
                return dis[end];
            }
        };

  • 0
    L

    Could anyone explain why DFS would not work?


  • 0
    C

    does dict always contain end in all test cases? if not, then when will your word be able to equal to end?


  • 0
    H

    Yes, it is possible that dict does not contain end. In this case, word will never get to be equal to end.

    I guess that you are wondering why my program will terminate in this case. This is because one entry will be popped out of q in each loop, finally q will be depleted and we will exit the while loop.


  • 0
    C

    For example the test case ["hot","dog",{"dot"}], the expected return value should be "hot"->"dot"->"dog" which is 3. But from your program I think the return value would be 0 because dis does not contain dog.


  • 0
    T

    while bfs find the shortest path between two nodes in an unweighted graph, dfs might not...


  • 0
    H

    I think it is because this problem is actually a shortest path problem but with all the edges equal to 1. In this case, the Dijkstra algorithm become a BFS. That is why BFS works.


  • 0
    P

    I think your code has a bug. If the end word is not in the dict, then your dis.count(end)==0, and the return result will be 0. This should be wrong! The test case for "hit", "cog", ["hot","dot","dog","lot","log"] will be 0 instead of 5. You should add a if condition that, if(newword==end) return dis.get(word)+1


  • 0
    J

    If using DFS to compute the shortest path, the order of visiting nodes should first be topologically sorted. If it is not, there may be loops in the DFS forest (recursive tree). For BFS, the visiting order is naturally topologically sorted.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.