# 0126. Word Ladder II
###### tags: `Leetcode` `Hard` `FaceBook` `DFS` `BFS` `Backtracking`
Link: https://leetcode.com/problems/word-ladder-ii/
## 思路
是[0127. Word Ladder](https://hackmd.io/2F_Qo1tWSH2QKrMp6USYEw)的变种，127题是找出有几条最短路径，126多了要把最短路径print出来
因为找最短路径一定是用BFS，产生所有路径一定是用backtracking，因此我们需要在BFS的时候建一个tree出来，由于在bfs的时候，我们已经构建出了每个单词的neighbor，因此只需要记录每个单词的level数，就可以做backtracking了
这一题找neighbor的方法和在127里面写的不一样，不是用map，而是把26个字母放在每个位子上都尝试一遍，这样找一个word的邻居的时间复杂度是O(26 * M^2) M是字符串长度，因为进了两层回圈之后，还要花O(M)，因为要产生新的字符串，才能去set里面看有没有contain
如果用127题的写法，构建map的时间复杂度是O(M^2 * N) N是word个数，然后每次找一个word的neighbor的时间复杂度是O(M^2)，因为对于每一个char位置，都需要用*替换，一共替换M次，同时每次替换因为要产生新的字符串，还需要花O(M)，因此相比之下，还是这题用的找neighbor的方法时间复杂度比较好
另外，一个de了很久的bug，是原本在57行后面，直接return了，没有先```curr.remove(curr.size-1)```，所以**backtracking一定要记得如果前面改了什么东西，return之前一定要改回去**
## Code

class Solution {
    Map<String, List<String>> adjacentList; 
    Set<String> dict;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        adjacentList = new HashMap<>();
        dict = new HashSet<>(wordList);
        Map<String, Integer> distance = new HashMap<>();
        bfs(beginWord, endWord, distance);
        List<List<String>> ans = new ArrayList<>();
        List<String> curr = new ArrayList<>();
        backtracking(beginWord, endWord, distance, curr, ans);
        return ans;
    }
    public void bfs(String beginWord, String endWord, Map<String, Integer> distance){
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        int dist = 0;
        boolean findEnd = false;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                String curr = q.poll();
                if(visited.contains(curr)) continue;
                visited.add(curr);
                distance.put(curr, dist);
                // System.out.println(curr+" "+dist);
                if(endWord.equals(curr)) findEnd = true;
                getNeighbors(curr, dict);
                q.addAll(adjacentList.get(curr));
            }
            dist++;
            if(findEnd){
                return;
            }
        }
    }
    public void getNeighbors(String word, Set<String> dict){
        List<String> neighbor = new ArrayList<>();
        char[] charArray = word.toCharArray();
        for(int i = 0;i < charArray.length;i++){
            for(char ch='a'; ch<='z';ch++){
                if(charArray[i] == ch) continue;
                char oldChar = charArray[i];
                charArray[i] = ch;
                if(dict.contains(String.valueOf(charArray))){
                    neighbor.add(String.valueOf(charArray));
                }
                charArray[i] = oldChar;
            }
        }
        adjacentList.put(word, neighbor);
    }
    public void backtracking(String startWord, String endWord, Map<String, Integer> distance, List<String> curr, List<List<String>> ans){
        curr.add(startWord);
        if(startWord.equals(endWord)){
            ans.add(new ArrayList<>(curr));
        }
        else{
            for(String next:adjacentList.get(startWord)){
                if(!distance.containsKey(next)) continue;
                if(distance.get(next) == distance.get(startWord)+1){
                    // System.out.println(startWord+" "+next);
                    backtracking(next, endWord, distance, curr, ans);
                }
            }
        }
        curr.remove(curr.size()-1);
    }
    
}