Java solution using a Node class to store parents of a word in the graph


  • 0
    C

    Instead using a map to store the graph relations, I directly wrote a simple Node class and store the parents of each word. The ideas are
    similar to the popular solutions. Detailed comments are in the code to help understand.

    class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> res = new LinkedList<>();    // the list to be returned
            Set<String> words = new HashSet<>(wordList);    // a set version of the given wordList
            Queue<String> q = new LinkedList<>();           // a queue for BFS
            Map<String, Node> nodeMap = new HashMap<>();    // map a word to a Node
            
            Set<String> visited = new HashSet<>();          // a set to store visited words in each level of the BFS. After searching the level, all the visited words stored in this set will be removed from the "words" set and this "visited" set is going to be cleared for the next level of BFS.
            Iterator<String> itr;
            q.offer(beginWord);
            words.remove(beginWord);        // the beginWord might be in the wordList. Remove it to avoid infinite recursion.
            
            while (!q.isEmpty()) {      // BFS
                int size = q.size();
                boolean flag = false;   // a flag to label if the path is found in this level.
                
                for (int i = 0; i < size; i++) {
                    if(searchNeighbors(q.poll(), endWord, q, res, words, visited, nodeMap)) flag = true; 
                }
                
                if (flag) {     // If the endWord is found, add all paths to the res and return.
                    addToRes(res, nodeMap.get(endWord), new LinkedList<String>());
                    return res;
                }
                
                itr = visited.iterator();    // remove all visited words in this level of BFS from "words" set and clear the "visited" set
                while (itr.hasNext()) {
                    words.remove(itr.next());
                }
                visited.clear();
            }
            
            return res;
        }
        
        class Node{
            Set<Node> parents;
            String word;
      
            Node(String word) {
                this.word = word;
                parents = new HashSet<Node>();
            }
        }
        
        boolean searchNeighbors(String beginWord, String endWord, Queue<String> q, List<List<String>> res, Set<String> words, Set<String> visited, Map<String, Node> nodeMap) { // search all neighbors in the "words" set
            char[] chars = beginWord.toCharArray();
            Node node = nodeMap.getOrDefault(beginWord, new Node(beginWord));
            nodeMap.put(beginWord, node);
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                for (int j = 1; j <= 25; j++) {
                    chars[i]++;
                    if (chars[i] > 'z') chars[i] -= 26;
                    String neighbor = new String(chars);
                    if (words.contains(neighbor)) {
                        q.offer(neighbor);
                        Node child = nodeMap.getOrDefault(neighbor, new Node(neighbor));
                        nodeMap.put(neighbor, child);
                        child.parents.add(node);
                        visited.add(neighbor);
                        if (neighbor.equals(endWord)) {
                            return true;
                        }
                    }
                }
                chars[i] = c;
            }
            return false;
        }
        
        void addToRes(List<List<String>> res, Node node, LinkedList<String> list) { // iterative method to add words from end to begin to a list as a path.
            LinkedList<String> newList = new LinkedList<>(list);
            newList.addFirst(node.word);
            if (node.parents.isEmpty()) {
                res.add(newList);
                return;
            }
            
            for (Node parent : node.parents) {
                addToRes(res, parent, newList);
            }
        }
    }
    

Log in to reply
 

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