题目描述

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

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

说明:

  • 如果不存在这样的转换序列,返回 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" 不在字典中,所以无法进行转换。

https://leetcode-cn.com/problems/word-ladder/

解法1

解法1使用BFS,为什么是Search解法呢?因为题目提示了,单词具有相同的长度,且只有小写字母,这样我们变换单词的每个字符就能形成新的单词,而不需要增删单词。为什么是BFS而不是DFS呢?因为要求最短转换序列,而BFS能够保证路径最短。如果我们使用DFS搜单词变化的路径,假设有两条长度不同的路径都能到达endWord,那么使用DFS可能先走入长路径,我们需要寻找出所有可行的路径,然后取他们最短的一个;而BFS是按照层次来搜索的,只要是遇到endWord,发现的路径一定是最短的。

那么搜索思路是什么呢?我们创建一个Queue,将beginWord加入队列。然后从队列中取出word,我们每次改变word的每个字符。因为字典里保存的单词都是小写字母,我们对每个字符枚举’a’ – ‘z’即可,然后检查新形成的单词是否存在于字典中。如果新单词存在于字典中,那么说明这个单词是中间单词,我们把他加入队列中,并从字典中移除;如果这个单词在字典中,且和endWord相等,那么我们就找到了最短路径

例1:

beginWord = "hit", 
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
图1 例1执行BFS过程

图1描述了BFS的过程,从hit作为beginWord开始,我们修改word的每一个字符,字符的变化范围是’a’-‘z’。如果形成的新的单词在wordList中存在,那么新单词就是变化路径的节点;如果新形成的单词不光在wordList中存在,且与endWord相等,那么我们就成功找到了一条转换序列。

为什么要从字典移除发现的单词呢?如果不从字典中移除,那么我们可能会出现a-b-a的情况,走了“回头路”,使得找到的路径不是最短路径。

令一点需要注意的是,题目要求计算的是转化序列的长度,而不是经过了几步变换。令一点需要注意的是,实现BFS时从queue取元素那个for循环应该逆序,这样我们才能够取得同一层次的word。如果我们顺序遍历,每次循环都会调用queue.size(),而在循环过程中queue的size是不断变化的,导致逻辑错误。如果想让for循环写法是顺序的,就要用另一个变量保存queue被修改前的长度,这样我们才能够访问同一层次的word。

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

        wordSet.remove(beginWord);
        queue.offer(beginWord);

        while (queue.size() > 0) {
            step++;

            for (int i = queue.size(); i > 0; i--) {
                char[] word = queue.poll().toCharArray();

                for (int x = 0; x < word.length; x++) {
                    char originC = word[x];

                    for (char c = 'a'; c <= 'z'; c++) {
                        word[x] = c;
                        String newWord = new String(word);

                        if(wordSet.contains(newWord)) {
                            if (newWord.equals(endWord))
                                return step + 1;

                            wordSet.remove(newWord);
                            queue.offer(newWord);
                        }
                    }

                    word[x] = originC;
                }
            }
        }

        return 0;
    }
}
pwrliang Algorithms, BFS ,

Leave a Reply

Your email address will not be published. Required fields are marked *