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

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

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

思路 2. (mapping 只存每個節(jié)點其下一層的節(jié)點?。。。。?/h5>

1. HashMap<String, List<String>> mapping: 存每個節(jié)點其下一層的節(jié)點
2. HashMap<String, Integer> distance: 存每個節(jié)點所在的層數(shù)（從0開始）

需要2步來處理

1. BFS得到mapping （需要distance的幫助）
2. 在mapping的基礎上用DFS找到所有路徑

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<> ();
        if (wordList == null || wordList.size () == 0 || !wordList.contains (endWord)) {
            return result;
        }
        
        // all neighbors of a word
        Map<String, Set<String>> mapOfWordAndNeighbors = new HashMap<> ();
        
        // distance from the beginWord
        Map<String, Integer> distance = new HashMap<> ();
        distance.put (beginWord, 0);
        
        // convert List into Set: to avoid timeout limited
        Set<String> wordSet = new HashSet<> (wordList);
        
        // 1. BFS to get words neighbors (only get its next layer's)
        getWordNeighborsMap (wordSet, beginWord, endWord, mapOfWordAndNeighbors, distance);
        
        if (mapOfWordAndNeighbors == null) {
            return result;
        }
        
        // 2. DFS to get all paths
        List<String> combinationEntry = new ArrayList<> ();
        combinationEntry.add (beginWord);
        getAllPaths (beginWord, endWord, mapOfWordAndNeighbors, combinationEntry, result);
        
        return result;
    }
    
    // using BFS to get word neighbor 
    // WARNING!!!!!: Don't use usedWords (HashSet<>), it's tough to handle the endWorld which has been visited
    // USE DISTANCE MAP, if a neighbor candidate is not in the distance map, or it's in the distance map but it is in the same layer (has the same distance)
    // then this neighbor a valid one, can put to the neighbor map 
    private void getWordNeighborsMap (Set<String> wordSet,
                                      String beginWord,
                                      String endWord,
                                      Map<String, Set<String>> mapOfWordAndNeighbors,
                                      Map<String, Integer> distance) 
    {
        Queue<String> currentLayer = new LinkedList<> ();
        Queue<String> nextLayer = new LinkedList<> ();
        currentLayer.offer (beginWord);
                
        while (!currentLayer.isEmpty ()) {
            String current = currentLayer.poll ();
            int currentDistance = distance.get (current);
            
            for (int i = 0; i < current.length (); i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (current.charAt (i) == ch)
                        continue;
                    
                    char[] tempChar = current.toCharArray ();
                    tempChar [i] = ch;
                    String tempNeighbor = String.valueOf (tempChar);
                    
                    if (wordSet.contains (tempNeighbor) && (!distance.containsKey (tempNeighbor) || distance.getOrDefault (tempNeighbor, -1)  == currentDistance + 1)) {
                        nextLayer.offer (tempNeighbor);

                        // 1) update the neighbor map
                        Set<String> neighbors = mapOfWordAndNeighbors.getOrDefault (current, new HashSet<> ());
                        neighbors.add (tempNeighbor);
                        mapOfWordAndNeighbors.put (current, neighbors);
                        
                        // 2) update the distance map
                        distance.put (tempNeighbor, currentDistance + 1);
                    } 
                }
            }
            
            if (currentLayer.isEmpty ()) {
                currentDistance ++;
                currentLayer = nextLayer;
                nextLayer = new LinkedList<> ();
            }  
        }
    }
    
    // DFS: traverse the map to get all paths
    
    private void getAllPaths (String currentWord,
                              String endWord,
                              Map<String, Set<String>> mapOfWordAndNeighbors, 
                              List<String> combinationEntry, 
                              List<List<String>> result)
    {
        if (currentWord.equals (endWord)) {
            result.add (new ArrayList<> (combinationEntry));
            return;
        }
        
        for (String neighbor : mapOfWordAndNeighbors.getOrDefault (currentWord, new HashSet<> ())) {
            combinationEntry.add (neighbor);
            getAllPaths (neighbor, endWord, mapOfWordAndNeighbors, combinationEntry, result);
            combinationEntry.remove (combinationEntry.size () - 1);
        }
    }
}

思路 1. (mapping 存每個節(jié)點所有鄰接點）

可以將這個word看做一個graph，找到其所有最短路徑，需要2個數(shù)據(jù)結(jié)構(gòu)。

1. HashMap<String, List<String>> mapping: 存每個節(jié)點的所有鄰接點
2. HashMap<String, Integer> distance: 存每個節(jié)點所在的層數(shù)（從0開始）

需要2個函數(shù)來處理
getGraphicInfo: 填充mapping和distance （BFS算法）

public void getGraphicInfo(HashMap<String, List<String>> mapping,
                               HashMap<String, Integer> distance,
                               String start,
                               Set<String> dict {…}

1. 用queue來存儲graphic的節(jié)點
2. queue中每個節(jié)點都取其neighbors
   a. 將該點的所有neighbors都放入mapping中對應的位置。
   b. 判斷該neighbor是否已在distance中，如不在則說明并未訪問過
   • 壓入queue
   • 在distance中加入該neighbor的distance == curStr的distance + 1

getLadder：遞歸找到所有path（DFS算法)

public void getLadder(HashMap<String, List<String>> mapping,
                          HashMap<String, Integer> distance,
                          String start, String curStr,
                          Set<String> dict,
                          List<List<String>> result,
                          List<String> path) {... }

從后往前找path

1. 每次進入該函數(shù)，path.add(curStr)
2. 判斷是否當前curStr節(jié)點==start，相等則代表找到了目標，將path加入到result中
3. 不相等，則沒有找到目標，還要繼續(xù)找：
   遍歷當前curStr的所有neighbors，如果是緊挨著的兩個節(jié)點（curStr distance = neighbor distance + 1），那么就是最短的路勁上的節(jié)點，則將該neighbor傳入getLadder（）作為curStr，遞歸繼續(xù)找
4. 前面全部完成后，需要回朔path，每一次path都remove掉尾巴上的元素。

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
     /*
     public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<>();
        if (dict == null) {
            return result;
        }
        
        //存每個節(jié)點的相鄰節(jié)點
        HashMap<String, List<String>> mapping = new HashMap<>();
        
        //存每個節(jié)點所在的層數(shù)
        HashMap<String, Integer> distance = new HashMap<>();
        
        dict.add(end);
        dict.add(start);
        distance.put(start, 0);
        
        //填充了mapping, distance 2個hashmap，得到了圖的所有信息
        // bfs算法
        getGraphicInfo(mapping, distance, start, dict);
        //得到path。getLadder為DFS算法，所以path（每條路徑）需從外部傳入
        List<String> path = new ArrayList<String>();
        getLadder(mapping, distance, start, end, dict, result, path);
        
        return result;
    }
    
    public void getGraphicInfo(HashMap<String, List<String>> mapping,
                               HashMap<String, Integer> distance,
                               String start,
                               Set<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        queue.add(start);
        
        for (String str : dict) {
            mapping.put(str, new ArrayList<String>());
        }
        
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            
            for (String str : getNeighbors(dict, cur)) {
                //填充mapping
                mapping.get(cur).add(str);
                
                //填充distance，distance的value是str節(jié)點的前一層節(jié)點（cur節(jié)點）的層數(shù)+1
                if (!distance.containsKey(str)) {
                    distance.put(str, distance.get(cur) + 1);
                    queue.add(str); //distance中沒有出現(xiàn)過的節(jié)點才是下一層需要加繼續(xù)queue的，如果已經(jīng)出現(xiàn)過了，則不要再放進queue了，因為是以訪問過的了
                }
            }
        }
    }
    
    public void getLadder(HashMap<String, List<String>> mapping,
                          HashMap<String, Integer> distance,
                          String start, String curStr,
                          Set<String> dict,
                          List<List<String>> result,
                          List<String> path) {
        //進入函數(shù)時就加一個節(jié)點
        path.add(curStr);
        if (curStr.equals(start)) {
            Collections.reverse(path);
            result.add(new ArrayList<>(path));
            Collections.reverse(path);
        } else {
            //找與當前節(jié)點相鄰的節(jié)點，判斷其是否是緊挨著的. 如果是則繼續(xù)DFS算法繼續(xù)找
            for (String str : mapping.get(curStr)) {
                if (distance.get(curStr) == distance.get(str) + 1) {
                    getLadder(mapping, distance, start, str, dict, result, path);
                }
            }
        }
        path.remove(path.size() - 1);
    }
    
    public List<String> getNeighbors(Set<String> dict, String cur) {
        List<String> result = new ArrayList<String>();
        
        for (int i = 0; i < cur.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                char[] temp = cur.toCharArray();
                if (cur.charAt(i) == c) {
                    continue;
                }
                temp[i] = c;
                String newStr = String.valueOf(temp);
                if (dict.contains(newStr)) {
                    result.add(newStr);
                }
            }
        }
        return result;
    }
}