词语序列

import java.util.*;

class Solution {
    /**
     *  双向BFS,减少容器的使用的情况下减少比较次数
     *  1. 创建两个初始集合，一个保存从前向后遍历的候选词
     *     另一个保存从后向前的候选词
     *  2. 两个集合取数量小的一个进行遍历，判断词的下一个词
     *     是否就在另一个集合中，如果在的话，返回当前计数+1
     *  3. 如果下一个词不在另一个集合，但是在总集合中，从总
     *     集合擦除该词，遍历后得到新的候选词集合，替换掉当前
     *     被遍历的集合后，计数+1
     *  4. 其他退出条件：如果某一个集合为空，代表没有找到路径
     *     返回0
     */   
    public int ladderLength(String beginWord, String endWord, HashSet<String> dict) {
        int max = dict.size()+1;
        Set<String> aSet = new HashSet<>(max); 
        Set<String> bSet = new HashSet<>(max);
        int count = 1;
        if(!dict.contains(endWord)) return 0;
        aSet.add(beginWord);
        bSet.add(endWord);
        dict.remove(beginWord);
        dict.remove(endWord);
        while(!aSet.isEmpty()&&!bSet.isEmpty()){
            if(aSet.size()>bSet.size()){
                Set<String> tmp = aSet;
                aSet = bSet;
                bSet = tmp;
            }
            Set<String> next = new HashSet<>(max);
            for(String word:aSet){
                char[] chars = word.toCharArray();
                for(int i=0; i<chars.length; i++){
                    for(char c='a'; c<='z'; c++){
                        if(c==chars[i]) continue;
                        char tmp = chars[i];
                        chars[i] = c;
                        String trans = new String(chars);
                        chars[i] = tmp;
                        if(bSet.contains(trans)){
                            return count+1;
                        }
                        if(dict.contains(trans)){
                            dict.remove(trans);
                            next.add(trans);
                        }
                    }
                }
            }
            aSet = next;
            count++;
        }
        return 0;
    }
}

import java.util.*;

class Solution {
    class Graph{
        String word;
        List<Graph> nexts;
        public Graph(String word, List<Graph> nexts){
            this.word = word;
            this.nexts = nexts;
        }
    }
    /*
     *  1. 首先判断下endWord是否在wordList中，不在的话根据题意直接返回0
     *  2. 创建邻接表将wordList以及beginWord放入图中
     *      邻接链表的创建原则是当两个词只差一个字母(题目已经限定所有词等长)
     *      问题转化为判断两个词只差一个单词
     *      可以遍历wordList，逐一将每一个字母用"*"替换，然后保存到Map中
     *      这个Map用替换掉某一位字母的字符串为key, 将所有只有某一位不同的单次保存在同一个List中
     *      建立过程记得通过第一步判断的数组索引保存好目标节点的引用，用于下一步最短路径的判断
     *  3. 建立好图以后，知道起始节点和目标节点，可以通过BFS求最短路径
     *      建一个新的Set保存已经遍历过的节点，因为是BFS，所以已经遍历过的节点，到目标节点的距离
     *      肯定比当前节点要短(当前图是无权无向图)，求最短路径不需要再去判断
     *      如果不存在路径，返回0
     *  遇到的几个坑：
     *      1) 起始词不能作为接龙词，不代表起始词不在词典中，要处理这种不在的情况
     *      2) 构建邻接关系时候，因为满足条件的结果中肯定包含自己(因为是用*替换的，包含原本字符的情况)，这个要排除
     */
    public int ladderLength(String beginWord, String endWord, HashSet<String> dict) {
        
        int n = dict.size();
        if(!dict.contains(endWord)) return 0;
        
        // 方便遍历操作，初始元素如果不在词典中要放入词典(题目是说初始元素不能作为接龙元素)
        dict.add(beginWord);
        Map<String, Graph> created = new HashMap<>(n+1);
        Map<String, List<Graph>> match = new HashMap<>(n+1);
        
        Graph start = new Graph(beginWord, new ArrayList<>());
        created.put(beginWord, start);
        Graph end = new Graph(endWord, new ArrayList<>());
        created.put(endWord, end);
        
        // 创建图的顶点以及保存按照每一位字符擦出的特征信息O(nm)
        for(String word:dict){
            if(!created.containsKey(word)){
                created.put(word, new Graph(word, new ArrayList<>()));
            }
            Graph vertex = created.get(word);
            char[] chars = new char[word.length()];
            word.getChars(0, word.length(), chars, 0);
            for(int i=0; i < chars.length; i++){
                char tmp = chars[i];
                chars[i] = '*';
                String m = new String(chars);
                if(!match.containsKey(m)){
                    match.put(m, new ArrayList<>());
                }
                match.get(m).add(vertex);
                chars[i] = tmp;
            }
        }   
        // 保存邻接信息O(n^2)，将之前遍历得到的所有只差一个字符的非本身元素保存到nexts中去
        for(String word:dict){
            Graph vertex = created.get(word);
            char[] chars = new char[word.length()];
            word.getChars(0, word.length(), chars, 0);
            for(int i=0; i < chars.length; i++){
                char tmp = chars[i];
                chars[i] = '*';
                List<Graph> mlist = match.get(new String(chars));
                chars[i] = tmp;
                // 接龙元素不能重复使用，不能自己指向自己
                for(Graph next:mlist){
                    if(next!=vertex){
                        vertex.nexts.add(next);
                    }
                }
            }
        }
        // 通过BFS找到从start到end的最短路径
        int min = 0;
        Set<Graph> searched = new HashSet<>(n+1);
        List<Graph> path = new ArrayList<>(n+1);
        Queue<List<Graph>> pathes = new LinkedList<>();
        path.add(start);
        pathes.add(path);
        searched.add(start);
        // 队列pathes中保存的需要继续遍历(还有可以后续顶点可以遍历)的待遍历路径
        while(!pathes.isEmpty()){
            List<Graph> curPath = pathes.remove();
            Graph last = curPath.get(curPath.size()-1);
            if(last == end){
                // min=0时代表无解
                min = min==0 ? curPath.size() : Math.min(min, curPath.size());
                continue;
            }
            for(Graph next:last.nexts){
                // 没有后续的未遍历顶点跳过
                if(!searched.contains(next)){
                    List<Graph> nextPath = new ArrayList<>(curPath);
                    nextPath.add(next);
                    pathes.add(nextPath);
                    searched.add(next);
                }
            }
        }
        return min;        
    }
}