# 0127. Word Ladder
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/word-ladder/

## 思路 $O(M^2N)$ $O(M^2N)$ M是单词长度 N是单词个数
先建构一个adjacentList，使得相差一个字母的word全部都存在hashmap的同一个value下，再做bfs
储存的方法是 拿到一个word，例如dog, 就会把他放到-og,d-g,do-里面

**注意空间复杂度，adjacentList的空间复杂度是O(M^2 * N) 对于每个key(一共有N个)，最多有M个neighbor，每个neighbor的长度是O(M）**

以下是方法二的注意事项
**注意在第7行和第30行用到的getOrDefault**
**第7行的使用可以减少if判断**
**第30行的使用可以防止找不到key的情况，也可以有效减少if判断**
## Code
以下两种方法只是找neighbor的方式不同
### 方法一

class Solution {
    Map<String, List<String>> adjacentList;
    Set<String> dict;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        adjacentList = new HashMap<>();
        dict = new HashSet<>(wordList);
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.add(beginWord);
        int depth = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                String currWord = q.poll();
                if(currWord.equals(endWord)){
                    return depth;
                }
                List<String> nextStrings = getNext(currWord);
                for(String next:nextStrings){
                    if(!visited.contains(next)){
                        q.add(next);
                        visited.add(next);
                    }
                }
            }
            depth++;
        }
        return 0;
    }
    private List<String> getNext(String currWord){
        char[] str = currWord.toCharArray();
        List<String> ans = new ArrayList<>();
        for(char c = 'a';c <= 'z';c++){
            for(int i = 0;i < str.length;i++){
                char oldChar = str[i];
                str[i] = c;
                if(dict.contains(String.valueOf(str))){
                    ans.add(String.valueOf(str));
                }
                str[i] = oldChar;
            }
        }
        return ans;
    }
}

### 方法二

class Solution {
    Map<String, List<String>> adjacentList;
    public void createAdjacent(List<String> words, int len){
        for(String word:words){
            for(int i = 0;i < len;i++){
                String newWord = word.substring(0,i)+'*'+word.substring(i+1,len);
                List<String> transform = adjacentList.getOrDefault(newWord, new ArrayList<String>());
                transform.add(word);
                adjacentList.put(newWord, transform);
            }
        }
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        adjacentList = new HashMap<>();
        int len = beginWord.length();
        createAdjacent(wordList, beginWord.length());
        
        Queue<Pair<String, Integer>> q = new LinkedList<>();
        q.add(new Pair(beginWord,1));
        
        Set<String> visited = new HashSet<>();
        
        while(!q.isEmpty()){
            Pair<String, Integer> node = q.poll();
            String word = node.getKey();
            int depth = node.getValue();
            int size = q.size();
            for(int i = 0;i < len;i++){
                String newWord = word.substring(0,i)+'*'+word.substring(i+1,len);
                for(String nextWord: adjacentList.getOrDefault(newWord, new ArrayList<>())){
                    if(nextWord.equals(endWord)) return depth+1;
                    if(!visited.contains(nextWord)){
                        visited.add(nextWord);
                        q.add(new Pair(nextWord, depth+1));
                    }
                }
            }
        }
                              
        return 0;
    }
}