Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.

Analysis

Code

public class Solution {
    List<List<String>> results;
    List<String> list;
    Map<String,List<String>> map;

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        results= new ArrayList<List<String>>();
        if (dict.size() == 0) return results;

        boolean found=false;            
        list = new LinkedList<String>();           
        map = new HashMap<String,List<String>>();

        Queue<String> queue= new ArrayDeque<String>();
        Set<String> unvisited = new HashSet<String>(dict);
        Set<String> visited = new HashSet<String>();

        queue.add(start);           
        unvisited.add(end);
        unvisited.remove(start);

        //BFS
        while (!queue.isEmpty()) {
            int qLen = queue.size();

            for (int i=0; i<qLen; i++){
                String word = queue.poll();
                for (String nextWords:getNextWords(word, unvisited)){
                if (visited.add(new_word)){//Key statement,Avoid Duplicate queue insertion
                    next++;
                    queue.add(new_word);
                }

                if (map.containsKey(new_word))//Build Adjacent Graph
                    map.get(new_word).add(word);
                else{
                    List<String> l= new LinkedList<String>();
                    l.add(word);
                    map.put(new_word, l);
                }

                if (new_word.equals(end)&&!found) found=true;  
            }
            }

            if (curr==0){
                if (found) break;
                curr=next;
                next=0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        }//End While

        backTrace(end,start);

        return results;        
    }

    //function to build results from map    
    private void backTrace(String word,String start){
        if (word.equals(start)){
            list.add(0,start);
            results.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        list.add(0,word);
        if (map.get(word)!=null)
            for (String s:map.get(word))
                backTrace(s,start);
        list.remove(0);
    }

    //返回所有和curr差一个字母，并且在dict里面的words
    //把每个字母替换为26个字母中的一个，检查是否在dict里面
    private Set<String> getNextWords(String curr, Set<String> dict) {
        Set<String> nextWords = new HashSet<String>();
        for (int i=0; i<curr.length(); i++){
            char[] chars = curr.toCharArray();
            for (char c = 'a'; c<='z'; c++){
                chars[i]=c;
                String temp = new String(chars);
                if (dict.contains(temp)) {nextWords.add(temp);}
            }
        }
        return nextWords;
    }

}

Note

• Need re-write this code, not fully understood!

Reference

Leetcode