[LeetCode]126. 单词接龙 II（java实现）转化成图论最短路问题

1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结

思路（bfs+dfs）：
我们将每次修改一个单词看成是一个节点到另一个节点的过程，那么每个节点连接起来能形成一个无向图（如下图所示，图与题中示例无关，仅作参考）。

因此我们将问题转化成求从 endWord 到 beginWord 的路径和最小的路径。

建图的两种方式

枚举所有单词对，然后判断是否可以通过改变一个字母相互转化，时间复杂度 O(n²L)

枚举每个单词，然后枚举该单词的每一位字母，再枚举这一位的所有备选字母，然后再判断改变后的字符串是否存在，时间复杂度 O(26nL²)。

如果 26L > n，则用第二种，否则用第一种。

建图、权值为1的最短路问题：用bfs初始化dist数组

队列初始化：将beginWord加到队列中队首元素依次出队，用str表示当前出队的单词bfs核心：当str出队时，将所有仅需要修改单词str一个字母就能得到的且存在于wordList中的单词new_str加到dist数组中，即dist[new_str] = dist[str] + 1将单词new_str加到队列中，继续执行步骤2直到队空或者遍历到endWord为止（因为遍历到endWord时，已经不需要再进行单词变换了）

建图后，维护一个数组 dist ，dist[str] 表示从单词 str 到起点的最短路径

利用得到的 dist 数组，从终点beginWord开始爆搜出所有的最短路径，用str表示当前单词

若发现 dis(str) 不存在，则没有最短路径；

否则枚举当前节点的邻接点 new_str ，如果 dist[str] + 1 == dist[new_str] 说明存在一条最短路径，最后一步是从 节点 str 走到 节点 new_str；

依此类推，爆搜每个单词，直到搜索到终点 endWord 为止，说明找到了一条从 beginWord 到 endWord 的最短路径。

注：我们在代码中用哈希表来模拟dist数组

---------------------------------------------------解法---------------------------------------------------：

class Solution {
    List> res = new ArrayList<>();
    List path = new ArrayList<>();
    Map dist=new HashMap<>();
    HashSet set = new HashSet<>();

    public List> findLadders(String beginWord, String endWord, List wordList) {
        // bfs队列queue
        Queue queue = new linkedList<>();
        // 初始化，将起点插到dist与queue中
        dist.put(beginWord,0);
        queue.add(beginWord);

        for(String s : wordList) set.add(s);
        
        // 建图，构建dist数组
        while(!queue.isEmpty()){
            // 取出队头元素
            String str = queue.poll();
            // 如果队头元素是endWord，不需要再进行单词变换了，终止建图
            if(str.equals(endWord)) break;

            // 单词转换
            // 枚举这个单词的每一位
            for(int i = 0;i < str.length();i++){
                // 存储当前单词
                StringBuilder sb = new StringBuilder(str);
                // 将每一位上的字母换成26个英文字母中的一个，再转换成新的字符串，看是否在给定的wordList中
                for(char c = 'a';c <= 'z';c++){
                    // 转换当前位上的字母为变量c
                    sb.setCharAt(i,c);
                    // 将变完的单词转换为String
                    String new_str = sb.toString();
                    // 如果新的单词在给定的wordList中，并且该单词还没有出现过，说明这个单词还没有被搜索过
                    if(set.contains(new_str) && !dist.containsKey(new_str)){
                        // 将这个单词加到dist中，其路径长度为原单词路径长度+1
                        dist.put(new_str,dist.get(str) + 1);
                        // 将这个单词加到队列中，准备进行下一层bfs
                        queue.add(new_str);
                    }
                }
            }
        }

        // 如果从beginWord不能转换成endWord，直接返回res
        if(!dist.containsKey(endWord)) return res;
        path.add(beginWord);
        dfs(beginWord,endWord);
        return res;
    }

    // 爆搜
    private void dfs(String str,String endWord){
        // 如果找到了最后一个单词，将当前路径加到res中
        if(str.equals(endWord)){
            res.add(new linkedList<>(path));
            return;
        }
        // 枚举当前单词
        for(int i = 0;i < str.length();i++){
            // 单词转换
            StringBuilder sb = new StringBuilder(str);
            for(char c = 'a';c <= 'z';c++){
                sb.setCharAt(i,c);
                String new_str = sb.toString();
                // 如果dist中存在这个单词并且新的单词与当前单词路径之差1，则可以加到path中
                if(dist.containsKey(new_str) && dist.get(new_str) == dist.get(str) + 1){
                    path.add(new_str);
                    dfs(new_str,endWord);
                    // 回溯
                    path.remove(path.size()-1);
                }
            }
        }
    }
}

可能存在的问题：

权值为1的最短路问题：bfs爆搜：dfs 6. 总结