Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

private void getNextWords(Map<String, Set<String>> nextWordsMap, String word, Set<String> dict) {
        char [] chars = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {           
            char old = chars[i]; 
            for (char c = 'a'; c <= 'z'; c++) {
                //do not add the current word
                if (c != old)  {
                    chars[i] = c;
                    String nextWord = new String(chars);                

                    if (dict.contains(nextWord)) {
                        Set<String> nextWords = nextWordsMap.get(word);
                        if (nextWords != null) {
                            nextWords.add(nextWord);
                        } else {
                            nextWords = new HashSet<String>();
                            nextWords.add(nextWord);
                            nextWordsMap.put(word, nextWords);
                        }
                    }     
                }                        
            }
            //revert the word back
            chars[i] = old;
        }
    }

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> results = new ArrayList<List<String>>();
        Queue<String> queue = new LinkedList<String>();
        Map<String, Integer> levelMap = new HashMap<String, Integer>();
        queue.add(start);
        levelMap.put(start, 1);
        //make sure the end is in dict
        dict.add(end);

        Map<String, Set<String>> nextWordsMap = new HashMap<String, Set<String>>();
        getNextWords(nextWordsMap, start, dict);
        // init adjacent graph        
        for(String word : dict){
            getNextWords(nextWordsMap, word, dict);
        }

        while (!queue.isEmpty()) {
            String wordPath = queue.poll();
            String[] words = wordPath.split(" ");
            String current = words[words.length-1];
            if (current.equals(end)) {                
                List<String> result = Arrays.asList(words);
                results.add(result);                
            } else {
                Set<String> nextWords = nextWordsMap.get(current);
                if (nextWords!=null) {
                    int nextLevel = words.length+1;
                    for (String nextWord : nextWords) {
                        //if the word has been used before then he can only be added to the same level
                        if (levelMap.get(nextWord)==null || nextLevel==levelMap.get(nextWord)) {
                            queue.add(wordPath + " " + nextWord);
                            if (levelMap.get(nextWord)==null) {
                                levelMap.put(nextWord, nextLevel);
                            }
                        }
                    }
                }                
            }
        }

        return results;
    }