题目：

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 listFor example,

Given:

beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]Return [

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

]

解答：

public class Solution {    List
    
     
      > result;    List
      
        list;    Map
       
        > map;    public List
        
         
          > findLadders(String beginWord, String endWord, Set
          
            wordList) { result = new ArrayList
           
            
             >(); if (wordList.size() == 0) return result; list = new LinkedList
             
              (); map = new HashMap
              
               >(); int curt = 1, next = 0; boolean found = false; Set
               
                 unvisited = new HashSet
                
                 (wordList); Set
                 
                   visited = new HashSet
                  
                   (); Queue
                   
                     queue = new ArrayDeque
                    
                     (); queue.add(beginWord); unvisited.add(endWord); unvisited.remove(beginWord); //BFS while (!queue.isEmpty()) { String word = queue.poll(); curt--; for (int i = 0; i < word.length(); i++) { StringBuilder sb = new StringBuilder(word); for (char ch = 'a'; ch <= 'z'; ch++) { sb.setCharAt(i, ch); String newWord = sb.toString(); if (unvisited.contains(newWord)) { if (visited.add(newWord)) { next++; queue.add(newWord); } if (!map.containsKey(newWord)) { map.put(newWord, new LinkedList
                     
                      ()); } map.get(newWord).add(word); if (newWord.equals(endWord) && !found) found = true; } } } if (curt == 0) { if (found) break; curt = next; next = 0; unvisited.removeAll(visited); visited.clear(); } } backTrace(endWord, beginWord); return result; } public void backTrace(String word, String beginWord) { if (word.equals(beginWord)) { list.add(0, beginWord); result.add(new ArrayList
                      
                       (list)); list.remove(0); return; } list.add(0, word); if (map.get(word) != null) { for (String s : map.get(word)) { backTrace(s, beginWord); } } list.remove(0); }}