单词接龙 II

126. 单词接龙 II

给定两个单词（beginWord 和 endWord）和一个字典 *wordList，找出所有从 *beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

1. 每次转换只能改变一个字母。

2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回一个空列表。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

本题要求的是最短转换序列，看到最短首先想到的就是BFS 。想到 BFS 就能想到图。我们需要建立图的模型：将每个单词抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明它们之间有一条双向边。因此只要把满足转换条件的点相连，就形成了一张图。如下图（来自Leetcode）

有了上图我们以 hit 为图的起点，以cog 为终点进行广度优先搜索，寻找 hit 到 cog 的最短路径。

方便起见，我们先给每一个单词标号，即给每个单词分配一个 id。创建一个由单词 word到 id 对应的映射 wordId，并将 beginWord 与 wordList 中所有的单词都加入这个映射中。之后我们检查 endWord 是否在该映射内，若不存在，则输入无解。我们可以使用哈希表实现上面的映射关系。

同理我们可以创建一个由对应 id 到 word 的映射 idWord，方便最后输出结果。由于 id 实际上是整数且连续，所以这个映射用数组实现即可。

接下来我们将 idWord 中的单词两两匹配，检查它们是否可以通过改变一个字母进行互相转换。如果可以，则在这两个点之间建一条双向边。

为了保留相同长度的多条路径，我们采用 cost 数组，其中 cost[i] 表示 beginWord 对应的点到第 i 个点的代价（即转换次数）。初始情况下其所有元素初始化为无穷大。

接下来将起点加入队列开始广度优先搜索，队列的每一个节点中保存从起点开始的所有路径。

对于每次取出的节点 now，每个节点都是一个数组，数组中的最后一个元素为当前路径的最后节点 last :

• 若该节点为终点，则将其路径转换为对应的单词存入答案;
• 若该节点不为终点，则遍历和它连通的节点（假设为 to ）中满足 cost[to] >= cost[now] + 1cost[to]>=cost[now]+1 的加入队列，并更新 cost[to] = cost[now] + 1cost[to]=cost[now]+1。如果 cost[to] < cost[now] + 1cost[to]<cost[now]+1，说明这个节点已经被访问过，不需要再考虑。

class Solution {
    private static final int INF = 1 << 20;
    private Map<String, Integer> wordId; //单词到 id 的映射
    private List<String> idWord; //id到单词的映射
    private List<Integer>[] edges; //图的边

    Solution(){
        wordId = new HashMap<>();
        idWord = new ArrayList<>();
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        int id = 0;
        // 将 wordList 所有单词加入 wordId 中 相同的只保留一个，并为每个单词分配一个 id。
        for(String word : wordList){
            if(! wordId.containsKey(word)){
                wordId.put(word, id++ );
                idWord.add(word);
            }
        }

        //若 endWord 不在 wordList 中则无解
        if(! wordId.containsKey(endWord)){
            return new ArrayList<>();
        }

        //把 beginWord 也加入 wordId 中
        if(! wordId.containsKey(beginWord)){
            wordId.put(beginWord, id++);
            idWord.add(beginWord);
        }

        //初始化存储边的数组
        edges = new ArrayList[idWord.size()];
        for(int i = 0; i < idWord.size(); i++){
            edges[i] = new ArrayList<>();
        }
        //添加边
        for(int i = 0; i < idWord.size(); i++){
            for(int j = i + 1; j < idWord.size(); j++){
                //如果两者可以通过转换得到 则在它们间建一条无向边
                if(transformCheck(idWord.get(i), idWord.get(j))){
                    edges[i].add(j);
                    edges[j].add(i);
                }
            }
        }

        int dest = wordId.get(endWord); //目的 id
        List<List<String>> res  = new ArrayList<>();//存答案
        int[] cost = new int[id];//到每个点的代价
        for(int i = 0; i < id; i++){
            cost[i] = INF;
        }

        //将起点加入队列，并将其cost 设置为 0 
        Queue<ArrayList<Integer>> q = new LinkedList<>();
        ArrayList<Integer> tmpBegin = new ArrayList<>();
        tmpBegin.add(wordId.get(beginWord));
        q.add(tmpBegin);
        cost[wordId.get(beginWord)] = 0;

        //广度优先搜索
    while(! q.isEmpty()){
        ArrayList<Integer> now = q.poll();
        int last = now.get(now.size() - 1);//最近访问的点
        if(last == dest){//若该点为终点则将其存入答案 res 中
            ArrayList<String> tmp = new ArrayList<>();
            for(int index : now){
                tmp.add(idWord.get(index));
            }
            res.add(tmp);
        }else{//该点不为终点 继续搜索
            for(int i = 0; i < edges[last].size(); i++){
                int to = edges[last].get(i);
                //此处 <= 目的在于把代价相同的不同路径全部保存下来
                if(cost[last] + 1 <= cost[to]){
                    cost[to] = cost[last] + 1;
                    //把 to 加入路径中
                    ArrayList<Integer> tmp = new ArrayList<>(now); tmp.add(to);
                    q.add(tmp);
                }
            }

        }
    }

    return res;
    }

    private boolean transformCheck(String str1, String str2){
        int diff = 0;
        for(int i = 0; i < str1.length() && diff < 2; i++){
            if(str1.charAt(i) != str2.charAt(i)){
                diff++ ;
            }
        }
        return diff == 1;
    }
}

时间复杂度：O(N^2C)。其中 N 为 wordList 的长度，C 为列表中单词的长度。空间复杂度：O(N^2)。