题目描述

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList，找到从 beginWord 到 endWord 的 最短转换序列 中的单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

输入：
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：5
解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2：

输入：
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出：0
解释：endWord “cog” 不在字典中，所以无法进行转换。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

---

问题分析

以第一个示例为例进行分析：

• beginWord = “hit”
• endWord = “cog”
• wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

如上图所示，可将该问题抽象为一个图，那么要找到 beginWord 到 endWord 的最短转换序列的单子数量，只需要进行一次BFS检索即可。

---

解决方案一：单向BFS

按照上图的规则进行广搜遍历即可：
最初代码如下：

/**
     * 解题思路：
     * 		使用level记录当前遍历到了第几层
     * 		用map标记上一层使用到的单词，在本层中不可重复使用
     * 		写一个函数来检查两个单词是不是只差一个字符，返回一个boolean
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // bfs的深度
        int level = 0;

        // 检查endWord是不是包含在wordList中
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 标记单词是不是已经使用过
        Set<String> map = new HashSet<>();
        Set<String> tmpMap = new HashSet<>();

        // 定义一个Queue来实现bfs
        Queue<String> queue = new ArrayDeque<>();
        queue.add(beginWord);

        while (!queue.isEmpty()) {

            /** 从前向后 */
            int count = queue.size();
            level++;

            // 将上一层bfs使用过的单词，在该层统一进行标记
            map.addAll(tmpMap);
            tmpMap.clear();

            while (--count >= 0) {

                // 拿出queue中的元素，并在list中查找与其仅有一个字符不同的单词
                String key = queue.remove();

                // 将key临时记录，并在当前循环结束之后放入map中记录，之后不再访问
                tmpMap.add(key);
				
				// 便利整个wordList，找到key可以通过一次变换得到的单词，如果该单词未被访问过，将其放入队列中
                for (String s : wordList) {
                    // 比较key和list中未曾访问过的某个元素是不是仅有一个字符不同
                    if (!map.contains(s) && checkDiff(key, s)) {
                        queue.add(s);
                        // 当前元素s等于endWord的时候，返回即可
                        if (s.equals(endWord)) {
                            return level + 1;
                        }
                    }
                }
            }
        }

        return 0;
    }

    /**
     * 检查key和s是不是只有一个字符不相同
     * @param key
     * @param str
     * @return 满足条件则返回true，否则返回false
     */
    private boolean checkDiff(String key, String str) {

        if (key == null || str == null) {
            return false;
        }

        int count = 0;
        int keyLen = key.length();
        int strLen = str.length();

        if (keyLen != strLen) {
            return false;
        }

        for (int i = 0; i < keyLen; i++) {
            if (key.charAt(i) != str.charAt(i)) {
                count++;
                if (count > 1) {
                    return false;
                }
            }
        }
        return count == 1;
    }

在leetcode提交后，超时

---

该方法未进行任何优化，时间复杂度极高。可以进行初步优化：

1. 检索key通过变化一个字符可变成的单词的时候，在全部wordList中检索，此处可以通过构建一个map存放key可以转化成的单词列表，比如用 Map<String, Set< String>> 来存储。

优化后的代码如下：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // bfs的深度
        int level = 0;
        wordList.add(beginWord);
        
        // 检查endWord是不是包含在wordList中
        if (!wordList.contains(endWord)) {
            return 0;
        }

		// 将数据进行初始化，用Map<String, Set<String>>来存储一个单词可通过改变一个字符转变成的单词集合
        Map<String, Set<String>> wordMap = new HashMap<>();
        for (String s: wordList) {
            Set<String> set = new HashSet<>();
            for (String ss : wordList) {
                if (checkDiff(ss, s)) {
                    set.add(ss);
                }
            }
            wordMap.put(s, set);
        }

        // 标记单词是不是已经使用过
        Set<String> map = new HashSet<>();
        Set<String> tmpMap = new HashSet<>();

        // 定义一个Queue来实现bfs
        Queue<String> queue = new ArrayDeque<>();
        queue.add(beginWord);

        while (!queue.isEmpty()) {

            /** 从前向后 */
            int count = queue.size();
            level++;

            // 将上一层bfs使用过的单词，在该层统一进行标记
            map.addAll(tmpMap);
            tmpMap.clear();

            while (--count >= 0) {

                // 拿出queue中的元素，并在list中查找与其仅有一个字符不同的单词
                String key = queue.remove();

                // 将key临时记录，并在当前循环结束之后放入map中记录，之后不再访问之
                tmpMap.add(key);
				
				// 在Map中获取与当前单词key直接相连的单词
                Set<String> list = wordMap.get(key);

                for (String s : list) {
                    // 找到list中未曾访问过的某个元素
                    if (!map.contains(s)) {
                        // 将s添加到队列中
                        queue.add(s);
                        if (s.equals(endWord)) {
                            return level + 1;
                        }
                    }
                }
            }
        }

        return 0;
    }

    /**
     * 检查key和s是不是只有一个字符不相同
     *
     * @param key
     * @param str
     * @return 满足条件则返回true，否则返回false
     */
    private boolean checkDiff(String key, String str) {

        if (key == null || str == null) {
            return false;
        }

        int keyLen = key.length();
        int strLen = str.length();

        if (keyLen != strLen) {
            return false;
        }



        int count = 0;

        for (int i = 0; i < keyLen; i++) {
            if (key.charAt(i) != str.charAt(i)) {
                count++;
                if (count > 1) {
                    return false;
                }
            }
        }

        return count == 1;
    }

该代码提交通过，运行时间为：

---

那么对该算法再次进行优化，从endWord开始向前遍历，其逆向的图与正向图的对比如下所示：

那么我们把正向搜索用的队列记为：queueBegin，而逆向搜索的队列记为：queueEnd。那么程序运行过程中，当其中一个队列的元素出现在另一个队列中的时候，结束并返回即可。

按照上述方式优化之后的结果：

---

另外一个可以优化的地方：
上边的方案中，我是在的另一个队列中检索当前BFS的节点是否存在，那么从上图可以看出来，队列中存在大量的冗余元素，且Queue的检索效率为线性的。另外，我们知道HashSet的查询效率是非常高的，而且还可以去重。那么可以使用两个Set集合来记录当前queueBegin和queueEnd中的元素，以提高检索（队列1中的元素出现在队列2中）效率。

优化后的代码如下：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        // 两个bfs的深度
        int level = 0;

        wordList.add(beginWord);

        // 检查endWord是不是包含在wordList中
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 将数据进行初始化，用Map<String, Set<String>>来存储一个单词可通过改变一个字符转变成的单词集合
        Map<String, Set<String>> wordMap = new HashMap<>();
        for (String s: wordList) {
            Set<String> set = new HashSet<>();
            for (String ss : wordList) {
                if (checkDiff(ss, s)) {
                    set.add(ss);
                }
            }
            wordMap.put(s, set);
        }


        // 标记单词是不是已经使用过 - 从begin处向后
        Set<String> usedBegin = new HashSet<>();

        // 标记单词是不是已经使用过 - 从end处向前
        Set<String> usedEnd = new HashSet<>();

        // 定义一个Queue来实现bfs
        Queue<String> queueBegin = new ArrayDeque<>();
        Queue<String> queueEnd = new ArrayDeque<>();
        queueEnd.add(endWord);
        queueBegin.add(beginWord);

        usedBegin.add(beginWord);
        usedEnd.add(endWord);

        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {

            level++;

            /** 两个队列,哪个短则让哪个往后搜 */
            if (queueBegin.size() > queueEnd.size()) {
                Queue<String> tmp = queueBegin;
                queueBegin = queueEnd;
                queueEnd = tmp;

                Set<String> set = usedBegin;
                usedBegin = usedEnd;
                usedEnd = set;
            }

            int count = queueBegin.size();

            while (--count >= 0) {

                // 拿出queue中的元素，并在list中查找与其仅有一个字符不同的单词
                String key = queueBegin.remove();

                Set<String> list = wordMap.get(key);
                if (list == null) {
                    continue;
                }

                for (String s : list) {
                    // 判断s是不是被使用过,使用过则跳过
                    if (usedBegin.contains(s)) {
                        continue;
                    }

                    // 判断在另一侧的queue中是不是包含
                    if (queueEnd.contains(s)) {
                        return level + 1;
                    }
                    // 将s添加到队列中
                    queueBegin.add(s);
                    usedBegin.add(s);
                }
            }
        }

        return 0;
    }

    /**
     * 检查key和s是不是只有一个字符不相同
     *
     * @param key
     * @param str
     * @return 满足条件则返回true，否则返回false
     */
    private boolean checkDiff(String key, String str) {

        if (key == null || str == null) {
            return false;
        }

        int keyLen = key.length();
        int strLen = str.length();

        if (keyLen != strLen) {
            return false;
        }

        int count = 0;

        for (int i = 0; i < keyLen; i++) {
            if (key.charAt(i) != str.charAt(i)) {
                count++;
                if (count>1){
                    return false;
                }
            }
        }
        return count == 1;
    }

运行结果（还是很高的，在建立wordMap结构的时间复杂度$O(n^2)$起步）：

---

最终优化方案：
看题解，在单词比对的时候使用了优化，具体思路是：
因为单词是由 a~z 这有限数量的字符组成的，可以遍历当前单词能转换成的所有单词，判断其是否包含在候选单词列表wordList中。

代码实现

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        // 两个bfs的深度
        int level = 0;

        wordList.add(beginWord);

        Set<String> wordListSet = new HashSet<>(wordList);

        // 检查endWord是不是包含在wordList中
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 将数据进行初始化，用Map<String, Set<String>>来存储一个单词可通过改变一个字符转变成的单词集合
        Map<String, Set<String>> wordMap = new HashMap<>();
        for (String s: wordList) {
            Set<String> set = new HashSet<>();

            char[] ss = s.toCharArray();
            for (int i = 0; i < ss.length; i++) {
                char tmpc = ss[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    ss[i] = c;
                    String str = new String(ss);
                    if (wordListSet.contains(str)) {
                        set.add(str);
                    }
                }
                ss[i] = tmpc;
            }
            wordMap.put(s, set);
        }


        // 标记单词是不是已经使用过 - 从begin处向后
        Set<String> usedBegin = new HashSet<>();

        // 标记单词是不是已经使用过 - 从end处向前
        Set<String> usedEnd = new HashSet<>();

        // 定义一个Queue来实现bfs
        Queue<String> queueBegin = new ArrayDeque<>();
        Queue<String> queueEnd = new ArrayDeque<>();
        queueEnd.add(endWord);
        queueBegin.add(beginWord);

        usedBegin.add(beginWord);
        usedEnd.add(endWord);

        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {

            level++;

            /** 两个队列,哪个短则让哪个往后搜 */
            if (queueBegin.size() > queueEnd.size()) {
                Queue<String> tmp = queueBegin;
                queueBegin = queueEnd;
                queueEnd = tmp;

                Set<String> set = usedBegin;
                usedBegin = usedEnd;
                usedEnd = set;
            }

            int count = queueBegin.size();

            while (--count >= 0) {

                // 拿出queue中的元素，并在list中查找与其仅有一个字符不同的单词
                String key = queueBegin.remove();

                Set<String> list = wordMap.get(key);
                if (list == null) {
                    continue;
                }

                for (String s : list) {
                    // 判断s是不是被使用过,使用过则跳过
                    if (usedBegin.contains(s)) {
                        continue;
                    }

                    // 判断在另一侧的queue中是不是包含
                    if (queueEnd.contains(s)) {
                        return level + 1;
                    }
                    // 将s添加到队列中
                    queueBegin.add(s);
                    usedBegin.add(s);
                }
            }
        }
        return 0;
    }

运行结果：

---

其实，可以不用构建wordMap，直接将其嵌入到循环中的话，效率其实也挺高的。因为在循环中的话，不需要对每个单词都进行检索一次，只会对那些从队列中取出来的元素检索。

代码：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        // 两个bfs的深度
        int level = 0;

        wordList.add(beginWord);

        Set<String> wordListSet = new HashSet<>(wordList);

        // 检查endWord是不是包含在wordList中
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 标记单词是不是已经使用过 - 从begin处向后
        Set<String> usedBegin = new HashSet<>();

        // 标记单词是不是已经使用过 - 从end处向前
        Set<String> usedEnd = new HashSet<>();

        // 定义一个Queue来实现bfs
        Queue<String> queueBegin = new ArrayDeque<>();
        Queue<String> queueEnd = new ArrayDeque<>();
        queueEnd.add(endWord);
        queueBegin.add(beginWord);

        usedBegin.add(beginWord);
        usedEnd.add(endWord);

        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {

            level++;

            /** 两个队列,哪个短则让哪个往后搜 */
            if (queueBegin.size() > queueEnd.size()) {
                Queue<String> tmp = queueBegin;
                queueBegin = queueEnd;
                queueEnd = tmp;

                Set<String> set = usedBegin;
                usedBegin = usedEnd;
                usedEnd = set;
            }

            int count = queueBegin.size();

            while (--count >= 0) {

                // 拿出queue中的元素，并在list中查找与其仅有一个字符不同的单词
                String key = queueBegin.remove();

                char[] keys = key.toCharArray();

                for (int i = 0; i < keys.length; i++) {
                    char tmp = keys[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        keys[i] = c;

                        String tmps = new String(keys);
                        if (usedBegin.contains(tmps)) {
                            continue;
                        }

                        if (usedEnd.contains(tmps)) {
                            return level + 1;
                        }

                        if (wordListSet.contains(tmps)) {
                            queueBegin.add(tmps);
                            usedBegin.add(tmps);
                        }
                    }
                    keys[i] = tmp;
                }
            }
        }
        return 0;
    }

这种优化之后，运行速度：