Easy to understand Java solution, one map and one queue


  • 0
    J

    The idea is basically similar to other posts, but I'm trying to write the code as clear and concise as possible.

    
    
        class QueueElement {
            String word;
            List<QueueElement> prev;
            int level;
            
            QueueElement(String word, int level) {
                this.word = word;
                this.level = level;
                prev = new ArrayList<>();
            }
            
        }
        
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> list = new ArrayList<>();
            if (beginWord.equals(endWord)) {
                List<String> childList = new ArrayList<>();
                childList.add(beginWord);
                list.add(childList);
                return list;            
            }
            
            HashMap<String, QueueElement> map = new HashMap<>();
            Queue<QueueElement> queue = new LinkedList<QueueElement>();
            QueueElement beginWordQE = new QueueElement(beginWord, 0);
            queue.offer(beginWordQE);
            map.put(beginWord, beginWordQE);
            wordList.add(endWord);  //This is important, otherwise the getNeighbors function won't be able to find the endWord
            int level = 0;
            boolean found = false;  //Boolean variable to track if a path is found
            
            while (!queue.isEmpty() && !found) {
                level++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    QueueElement qe = queue.remove();
                    //Get all the neighbor words from the word list.
                    List<String> neighbors = getNeighbors(qe.word, wordList);
                    for (String neighbor : neighbors) {
                        //If we have found the end word, then we set found to true, and add the end word to the map.
                        if (neighbor.equals(endWord)) {
                            found = true;
                            QueueElement endWordQE = map.getOrDefault(endWord, new QueueElement(endWord, level));
                            map.putIfAbsent(endWord, endWordQE);
                            endWordQE.prev.add(qe);
                        }
                        //If we have already visited the neighbor word before, we need to check whether the level of the 
                        //neighbor is the same as the current level, i.e. the neighbor is generated by this for loop.
                        //If that's the case, then we can add the current QE to the prev array. Otherwise, we have generated
                        //the neighbor word before, and we should just ignore it.
                        else if (!map.containsKey(neighbor)) {
                            QueueElement neighborQE = new QueueElement(neighbor, level);
                            map.put(neighbor, neighborQE);
                            neighborQE.prev.add(qe);
                            queue.offer(neighborQE);
                        }
                        else {
                            QueueElement neighborQE = map.get(neighbor);
                            if (neighborQE.level == level) { 
                                neighborQE.prev.add(qe);                            
                            }
                        }
                    }
                }
            }
            
            if (!found) return list;  //Need to quit it here, otherwise dfs should check whether qe is null.
            LinkedList<String> childList = new LinkedList<>();
            childList.add(endWord);
            dfs(list, childList, map, endWord);
            return list;
        }
        
        private void dfs(List<List<String>> list, LinkedList<String> childList, HashMap<String, QueueElement> map, String curWord) {
            QueueElement qe = map.get(curWord);
            if (qe.prev.size() == 0) {
                LinkedList<String> newList = new LinkedList<>();
                newList.addAll(childList);
                list.add(newList);
                return;
            }
            
            for (QueueElement prevQE : qe.prev) {
                childList.addFirst(prevQE.word);
                dfs(list, childList, map, prevQE.word);
                childList.removeFirst();
            }
            
        }
        
        private List<String> getNeighbors(String word, Set<String> wordList) {
            List<String> list = new ArrayList<>();
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char curCh = chars[i];
                for (char newCh = 'a'; newCh <= 'z'; newCh++) {
                    if (curCh == newCh) continue;
                    chars[i] = newCh;
                    String s = String.valueOf(chars);
                    if (wordList.contains(s)) list.add(s);
                    chars[i] = curCh;
                }
            }
            return list;
        }
    

Log in to reply
 

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