Java BFS ; beats 83%


  • 1
    L

    A bit tricky in case you want to avoid TLE. Firstly the the dictionary is a list that slows down searches. Secondly, the string manipulation could be best used using a char array and a temporary string could be avoided.

    The basic algorithm will be to add all the possible valid words into the queue and iterate from all options. By nature, it will be shortest since we are not traveling in depth. It means that we don't know anything special to find the shortest path since all paths have the same weight (i.e. 1 as the distance between two words).

    As an example:

    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log","cog"]
    As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

    We will start with all possible transformations of "hit" that are found in dictionary. To mark it as visited, it is best to delete the word from dictionary when we add the words. A transformation from "hit" will find "hot" in the dictionary and add to the queue. Later, "hot" will find "dot" and "lot" and add to the queue. The queue will keep both "dot" and "lot" at the same level and do searches to determine the level of "cog" from there. It is easier to manage the level using a wrapper class that will abstract both string and the len.

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if(beginWord==null || endWord==null || wordList.isEmpty()) {
                return 0;
            }
            Set<String> words = new HashSet<>();
            for (String s : wordList) {
                words.add(s);
            }
    
            
            //A BFS is naturally the shorter path.
            Queue<Wrapper> queue = new LinkedList<>();
            queue.add(new Wrapper(beginWord));
            words.remove(beginWord);
            while(!queue.isEmpty()) {
                Wrapper wrapper = queue.poll();
                String word = wrapper.s;
                if(word.equals(endWord)) {
                    return wrapper.len;
                }
                char[] arr = word.toCharArray();
                for(int i=0;i<arr.length;i++) {
                    for(char c = 'a' ;c<='z';c++) {
                        char orig = arr[i];
                        arr[i]=c;
                        String s = new String(arr);
                        if(words.remove(s)) {
                            queue.add(new Wrapper(s,wrapper.len+1));
                        }
                        arr[i]=orig;
                    }
                }            
            }
            
            return 0;
        }
        private static class Wrapper {
            private String s;
            private int len;
            Wrapper(String s) {
                this.s = s;
                this.len=1;
            }
            Wrapper(String s, int len) {
                this.s = s;
                this.len=len;
            }
            
        }
    

Log in to reply
 

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