class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if(wordSet.isEmpty() || !wordSet.contains(endWord)){
            return 0;
        }
        int length = beginWord.length();
        int res = 1;
        Set<String> visite = new HashSet<>();
        visite.add(beginWord);
        Deque<String> que = new LinkedList<>();
        que.addLast(beginWord);
        while(!que.isEmpty()){
            int size = que.size();
            while(size-- > 0){
                String word = que.pollFirst();
                char[] chs = word.toCharArray();
                for(int i=0;i<length;i++){
                   for(char c='a'; c<='z';c++){
                       char pre = chs[i];
                       chs[i] = c;
                       String newWord = String.valueOf(chs);
                       if(newWord.equals(endWord)){
                           return res+1;
                       }
                       if(visite.add(newWord) && wordSet.contains(newWord)){
                           que.addLast(newWord);
                       }
                       chs[i] = pre;
                   } 
                }
            }
            res++;
        }
        return 0;
    }
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String>wordSet = new HashSet<String>(wordList);
        if(wordSet.isEmpty() || !wordSet.contains(endWord)) return 0;
        Deque<String> queue = new LinkedList<String>();
        queue.addLast(beginWord);
        // 记录单词的长度，这里每个单词都是一样长的
        int N = beginWord.length();
        Map<String, Integer> map = new HashMap<>(); //记录单词对应路径长度
        map.put(beginWord, 1);
        while(!queue.isEmpty()){
            String word = queue.pollFirst();
            int path = map.get(word);
            char [] chs = word.toCharArray();
            for(int i=0; i<N;i++ ){
                for(char k='a'; k<='z';k++){
                    char pre = chs[i];
                    chs[i] = k;
                    String newWord = String.valueOf(chs);
                    if(newWord.equals(endWord)){
                        return path+1;
                    }
                    if(wordSet.contains(newWord) && !map.containsKey(newWord)){
                        map.put(newWord,path+1);
                        queue.addLast(newWord);
                    }
                    chs[i] = pre;
                }
            }
        }
        return 0;
    }
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordListInput) {
        // 比起朴素BFS多了两个队列，还有一个记录经过的Set
        Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>();
        Set<String> wordList = new HashSet<>(wordListInput);
        Set<String> visited = new HashSet<>();
        if(!wordList.contains(endWord)) return 0;
        int step =1, N = beginWord.length();
        beginSet.add(beginWord);
        endSet.add(endWord);
        // 注意只有两边都不为空才继续循环，否则就说明两个不可能有交集
        while((!beginSet.isEmpty() && !endSet.isEmpty())){
            Set<String> nextSet = new HashSet<>();
            for(String word: beginSet){
                char[] chs = word.toCharArray();
                for(int i=0;i<N;i++){
                    for(char c ='a';c<='z';c++){
                        char pre = chs[i];
                        chs[i] = c;
                        String nextWord = new String(chs);
                        // ?这是为什么能确定结束呢，endSet是从后面开始查找
                        // nextWord是变化的下一个单词，
                        // 因为我们是要找到他们两个集合的交集即可，endSet是对立的，只要EndSet中有nextWord就代表下一次循环就到达了endSet
                        if(endSet.contains(nextWord)) return step+1;
                        if(visited.add(nextWord)&&wordList.contains(nextWord)){
                            nextSet.add(nextWord);
                        }
                        chs[i] =pre;
                    }
                }
            }
            // 选择更小的一端开始
            if(endSet.size() <nextSet.size()){
                    beginSet = endSet;
                    endSet = nextSet;
            }else beginSet = nextSet;
                step++;
        }
        return 0;
    }
}