题目链接

leetcode在线oj题——单词接龙

题目描述

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

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 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 中的所有字符串 互不相同

解题思路

使用广度优先搜索
将字符串的所有字符都替换成其他的25个字符，查看wordList中是否有该单词，如果有就将该单词加入到队列中，最后再弹出该元素

例如：先将beginword加入到队列中

对hit的每一位的字符都进行遍历，将其变成其他的25个字母，例如先是hit的’h’，变成ait，发现ait并不在wordList中，继续变成bit…
第一个字符变换了25个字符都没有wordList中的字符串与之匹配

继续变换第二个字符‘i’，先是变成hat，然后是hbt…

一直将所有字符都替换查看是否匹配，如果匹配就将其放到队列里

最后只有将第二个字符变成o才有hot与之匹配，这时将hot放入队列，step++，将队列中的hit取出

然后继续将队列中的所有元素都拿出来，分别变换字符查看是否有匹配的，如果有并且没有遍历过，就放入队列中

继续重复上面的操作

继续重复

最终找到单词cog，返回step = 5

代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int step = 1;
        Queue<String> queue = new LinkedList<>();
        HashSet<String> isUsed = new HashSet<>();
        HashSet<String> dict = new HashSet<>();

        //添加第一个单词
        queue.offer(beginWord);
        isUsed.add(beginWord);

        //将链表转换为哈希表
        for (int i = 0; i < wordList.size(); i++) {
            dict.add(wordList.get(i));
        }

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size != 0){
                String curString = queue.poll();
                if(curString.equals(endWord)){
                    return step;
                }

                //修改单词中的一个字符
                for (int i = 0; i < curString.length(); i++) {
                    StringBuffer tmp = new StringBuffer(curString);
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        tmp.setCharAt(i,ch);
                        String newString = tmp.toString();

                        //判断新的单词是否在词典中,并且没有搜索过
                        if(!isUsed.contains(newString) && dict.contains(newString)){
                            queue.offer(newString);
                            isUsed.add(newString);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}