Using BFS, easy to understand ( Java )


  • 0
    R
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            ArrayList<List<String>> result = new ArrayList<List<String>>();
            HashMap<String, ArrayList<String>> neighbors  = new HashMap<String, ArrayList<String>>();
            Queue<String> queue = new LinkedList<String>();
            HashMap<String, Integer> dist = new HashMap<String, Integer>();
    
            queue.add(beginWord);
            dist.put(beginWord, 0);
    
            while (!queue.isEmpty()) {
                String word = queue.poll();
                if(word.equals(endWord)) {
                    ArrayList<String> path = new ArrayList<String>();
                    findPath(beginWord, endWord, path, dist, neighbors, result);
                    return result;
                }
    
                for(String s: getNextWords(word)) {
                    if(wordList.contains(s)) {
                        if(!neighbors.containsKey(word)) {
                            neighbors.put(word, new ArrayList<String>());
                        }
                        neighbors.get(word).add(s);
    
                        if(!dist.containsKey(s)) {
                            queue.add(s);
                            dist.put(s, dist.get(word) +1);
                        }
                    }
                }
            }
    
            return result;
        }
    
        private List<String> getNextWords(String word) {
            ArrayList<String> result  = new ArrayList<String>();
            for(int i = 0; i < word.length(); i++) {
                char[] chars = word.toCharArray();
                for(char x = 'a'; x <= 'z'; x++) {
                    chars[i] = x;
                    result.add(new String(chars));
                }
            }
    
            return result;
        }
    
        private void  findPath(String word, String endWord, ArrayList<String> path, HashMap<String, Integer> dist, HashMap<String, ArrayList<String>> neighbors, ArrayList<List<String>> result) {
            path.add(word);
            if(word.equals(endWord)) {
                result.add(new ArrayList<String>(path));
            }
            else {
                if(neighbors.get(word) != null) {
                    for (String neighbor : neighbors.get(word)) {
                        if (dist.get(neighbor) == dist.get(word) + 1) {
                            findPath(neighbor, endWord, path, dist, neighbors, result);
                        }
                    }
                }
            }
            path.remove(path.size()-1);
        }
    }

Log in to reply
 

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