題目：

給定兩個單詞（beginWord和 endWord）和一個字典，找到從beginWord 到endWord 的最短轉(zhuǎn)換序列的長度。轉(zhuǎn)換需遵循如下規(guī)則：

　　每次轉(zhuǎn)換只能改變一個字母。
　　轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞。
說明:

　　如果不存在這樣的轉(zhuǎn)換序列，返回 0。
　　所有單詞具有相同的長度。
　　所有單詞只由小寫字母組成。
　　字典中不存在重復的單詞。
　　你可以假設 beginWord 和 endWord 是非空的，且二者不相同。

示例1：

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

輸出: 5

解釋: 一個最短轉(zhuǎn)換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的長度 5。

示例2：

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

輸出:0

解釋:endWord "cog" 不在字典中，所以無法進行轉(zhuǎn)換。

分析：

　　目標是找到從beginWord 到endWord 的最短轉(zhuǎn)換序列的長度。本質(zhì)就是求最短路徑，而且中間單詞必須位于字典中，不能是其他的，同時根據(jù)題意可以endWord也必須在字典中，否則就沒辦法進行最后一步的轉(zhuǎn)換，如果endWord不在字典中，那就不存在從beginWord 到endWord的最短轉(zhuǎn)換序列，返回值也就為0。

　　這些單詞的長度都一樣，一次轉(zhuǎn)換只能轉(zhuǎn)換一個字母，也就是說當前單詞和轉(zhuǎn)換后的單詞不同的地方只在某一個字符處，其他地方的字符都必須是相同的。那么我們可以采取BFS算法進行搜索：

　　　　從beginWord開始，其作為第一層，序列長度設為1，從字典中尋找所有與其相差只有一個字母且未被訪問的單詞放入BFS的下一層結(jié)點集合中；

　　　　當前層遍歷完成之后，序列長度加1，然后進入下一層的遍歷，要求在當前的序列長度下將一層的所有結(jié)點遍歷完畢（出棧），而至于每一層究竟有多少個結(jié)點，這在開始每一層的遍歷之前會先計算出來；

　　　　重復以上的操作，第一次遇到endWord時，就將當前序列長度加1，然后立即返回。

代碼：

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

        if (!wordList.contains(endWord)){
            return 0;
        }

        boolean[] isVisited = new boolean[wordList.size()];
        LinkedList<String> queue = new LinkedList<>();

        queue.offer(beginWord);
        int count = 0;
        String flag = "";
        while (!queue.isEmpty()){

            int unum = queue.size();
            count++;
            while (unum-- > 0){

                String cur = queue.poll();

                for (int i = 0; i < wordList.size(); i++) {

                    if (cur.length() - commonStr(cur,wordList.get(i)) == 1 && !isVisited[i]){
                        isVisited[i] = true;
                        queue.offer(wordList.get(i));
                        if (wordList.get(i).equals(endWord)){
                            flag = wordList.get(i);
                            return count + 1;
                        }
                    }
                }
            }

        }
        return flag.equals(endWord) ? count:0;
    }

    private int commonStr(String str1,String str2){

        int length = 0;
        int i = 0;
        int j = 0;

        while (i < str1.length() && j < str2.length()){

            if (str1.charAt(i) == str2.charAt(j)){
                length++;

            }
            i++;
            j++;
        }
        return length;
    }

總結(jié)

以上是生活随笔為你收集整理的单词接龙（力扣第127题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。