Java Solution using Dijkstra's algorithm, with explanation


  • 55
    J
        public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
            Set<String> reached = new HashSet<String>();
            reached.add(beginWord);
            wordDict.add(endWord);
            int distance = 1;
            while (!reached.contains(endWord)) {
                Set<String> toAdd = new HashSet<String>();
                for (String each : reached) {
                    for (int i = 0; i < each.length(); i++) {
                        char[] chars = each.toCharArray();
                        for (char ch = 'a'; ch <= 'z'; ch++) {
                            chars[i] = ch;
                            String word = new String(chars);
                            if (wordDict.contains(word)) {
                                toAdd.add(word);
                                wordDict.remove(word);
                            }
                        }
                    }
                }
                distance++;
                if (toAdd.size() == 0) return 0;
                reached = toAdd;
            }
            return distance;
        }
    

    Basically I keep two sets of words, one set reached that represents the borders that have been reached with "distance" steps; another set wordDict that has not been reached. In the while loop, for each word in the reached set, I give all variations and check if it matches anything from wordDict, if it has a match, I add that word into toAdd set, which will be my "reached" set in the next loop, and remove the word from wordDict because I already reached it in this step. And at the end of while loop, I check the size of toAdd, which means that if I can't reach any new String from wordDict, I won't be able to reach the endWord, then just return 0. Finally if the endWord is in reached set, I return the current steps "distance".

    The idea is that reached always contain only the ones we just reached in the last step, and wordDict always contain the ones that haven't been reached. This is pretty much what Dijkstra's algorithm does, or you can see this as some variation of BFS.

    ps: I get TLE at the first two submissions, because when I check if wordDict has any matches with reached set, I use two for loops and determine if any pair of words differ by one. That's a huge slow-down because it'll takes m (size of reached) * n (size of wordDict) * l (length of words) time, while in this solution, it takes 26 * l * m time. So when n is huge, this solution will be (n/26) times faster.


  • 27
    C

    I think we can use a queue to replace the reached set, by which we can avoid duplicate check?

    public class Solution {
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);
            wordList.add(endWord);
            wordList.remove(beginWord);
            int level = 1;
            while(!queue.isEmpty()){
                int size = queue.size();
                for(int i=0;i<size;i++){
                    String str = queue.poll();
                    if(str.equals(endWord))return level;
                    for(String neighbor : neighbors(str,wordList)){
                        queue.offer(neighbor);
                    }
                }
                level++;
            }
            return 0;
        }
        
        public List<String> neighbors(String s, Set<String> wordList){
            List<String> res = new LinkedList<>();
            for(int i=0;i<s.length();i++){
                char [] chars = s.toCharArray();
                for(char ch = 'a'; ch <= 'z'; ch++){
                    chars[i] = ch;
                    String word = new String(chars);
                    if(wordList.remove(word)){
                        res.add(word);
                    }
                }
            }
            return res;
        }
    }

  • 0
    L

    sorry, I don't understand what you said about the time complexity. I think it takes 26 * l * m *n time since it needs to judge if wordDict contains word. However, it is indeed faster.


  • 1
    J

    There's no n in this equation because searching a word in the String set is O(1) operation.


  • 0
    L

    I understand now. Thank you!


  • 0
    M

    Nice Job.I get TLE becase i compare it with all the string in the dict.


  • 1
    H

    Elegant solution! But this is not as fast as bidirectional BFS solution


  • 0
    H

    I'm just curious why is this algorithm an instance of Dijkstra's rather than vanilla BFS? Every edge has weight 1 right?


  • 3

    @charlie.chen good idea to modularize the neighbor find part! However, I think the duplicate check is avoided, not because of whether queue or set is used, but how you find the neighbors of a word. When the neighbor string is found, it is removed from wordList. So this neighbor string won't be added again by another word.


  • 0
    H

    This is equivalent to BFS.


  • 2

    Well, I think it's same to unidirectional BFS. Correct me if I'm wrong.


  • 0
    J

    @shuangling I think this is the same way using a HashSet to check whether a nextWord is already been checked or not. If a nextWord has been put into HashSet once, then rest of the word neighbors won't use it.


  • 0
    H

    @charlie.chen
    @Joshua924
    Thank you both for sharing the solutions. While both solution are very good and very readable, one thing I can think of to have it fail fast is to add the corner case check at the beginning.
    if (beginWord == null || endWord == null || beginWord.length() != endWord.length()) return 0;
    Thanks.


  • 1
    J

    @hieu.trinh
    I've been thinking about this kind of "simplifying" logic for some time. In my opinion, if the main logic flow will not fail with the corner cases (e.g. you loop through a collection when the size of the collection can be 0), you shouldn't need to add the corner case check. True it will return right away, but if it will return a few computations later if you don't provide it. The time difference there is very negligible.

    I would be happy to lose that little piece of time for the cleanness, conciseness and readability of code.

    Just my own thoughts.


  • 1
    S

    Now this solutions is TLE...


  • 1
    F

    @Joshua924 I want say that this is not a Dijkstra's algorithm, it's just a BFS to find the shortest path, due to it's not a DAG


  • 1
    X

    why do you write the code

    wordDict.add(endWord);   
    

    I can't fugure it!


  • 1
    C

    So how this code exactly find the shortest path?? It does not, for this input:
    {"b", "c"} beginWord = "a", endWord = "c", it returns 2. Am I missing something?


  • 0
    R

    I think the time complexity is 26 to the power of l (length of the word) and not 26 * l


  • 0
    M

    For unweighted graph, this is more or less a BFS. Regardless for the graph initialization. For BFS the time complexity is O(V + E) is normal queue is used. For Dijkstra algorithm we typically use a PriorityQueue which results in a O(E + V logV) if the pq is implemented by the Fibbonacci heap. Time complexity could be even worse O(ElogV) if we use binary heap for the Dijkstra algorithm.


Log in to reply
 

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