Leetcode-127-单词接龙

Leecode-127-单词接龙

思路：BFS/双向BFS

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

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

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

示例 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" 不在字典中，所以无法进行转换。

题解

• 无向图中两个顶点之间的最短路径的长度，可以通过广度优先遍历得到；
• 为什么 BFS 得到的路径最短？可以把起点和终点所在的路径拉直来看，两点之间线段最短；
• 已知目标顶点的情况下，可以分别从起点和目标顶点（终点）执行广度优先遍历，直到遍历的部分有交集，这是双向广度优先遍历的思想。

分析题意：

「转换」意即：两个单词对应位置只有一个字符不同，例如 “hit” 与 “hot”，这种转换是可以逆向的，因此，根据题目给出的单词列表，可以构建出一个无向（无权）图；

• 如果一开始就构建图，每一个单词都需要和除它以外的另外的单词进行比较，复杂度是 O(N O(NwordLen)，这里 N 是单词列表的长度；
• 为此，我们在遍历的一开始，把所有单词放入一个哈希表中，然后在遍历的过程中构件图，每一次得到在单词列表里可以转换的单词，复杂度是O(26×wordLen)，借助哈希表，找到邻居与 N 无关；
• 使用BFS ： 所需要的辅助数据结构是
  • 队列
  • visited 集合
    • 说明：可以直接在 wordSet (由 wordList 放进集合中得到)里做删除
    • 但更好的做法是新开一个哈希表，遍历过的字符串放进哈希表里。
    • 这种做法具有普遍意义。绝大多数在线测评系统和应用场景都不会在意空间开销。

方法一 ： 广度优先遍历

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 第 1 步：先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);


        // 第二步 ： 图的广度优先遍历,必须使用队列和表示访问过的visited 访问过数据的哈希表
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        // 第三步： 开始进行广度优先遍历，包含起点，因此起点的初始化步数为1
        int step = 1;
        while(!queue.isEmpty()){
            int curSize = queue.size();
            for(int i = 0;i < curSize;i++){
                // 依次遍历当前队列中的单词
                String currWord = queue.poll();
                // 如果currWord 能够修改依次字符便和 endWord 相同，那么立即返回step + 1即可
                if(changeWordEveryOneLetter(currWord,endWord,queue,visited,wordSet)){
                    return step + 1;
                }
            }
            step++;
        }
        // 找不到的话返回0
        return 0;
    }

    private boolean changeWordEveryOneLetter(String currentWord, String endWord,
                                             Queue<String> queue, Set<String> visited, Set<String> wordSet) {
        char[] charArray = currentWord.toCharArray();

        for (int i = 0; i < endWord.length(); i++) {
            // 先保存，然后恢复
            char originChar = charArray[i];
            for (char k = 'a'; k <= 'z'; k++) {
                if (k == originChar) {
                    continue;
                }
                charArray[i] = k;
                String nextWord = String.valueOf(charArray);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        return true;
                    }
                    if (!visited.contains(nextWord)) {
                        queue.add(nextWord);
                        // 注意：添加到队列以后，必须马上标记为已经访问
                        visited.add(nextWord);
                    }
                }
            }
            // 恢复
            charArray[i] = originChar;
        }
        return false;
    }
}

方法二： 双向广度优先遍历

参考题解 ： https://leetcode-cn.com/problems/word-ladder/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/

打赏