程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Word Ladder

leetcode筆記:Word Ladder

編輯:C++入門知識

leetcode筆記:Word Ladder


一. 題目描述

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary

For example, Given:

start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]

As one shortest transformation is ”hit” -> ”hot” -> ”dot” -> ”dog” -> ”cog”, return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

二. 題目分析

 

可以將這道題看成是一個圖的問題。我們將題目映射到圖中,頂點是每個字符串,然後兩個字符串如果相差一個字符則進行連邊。我們的字符集只有小寫字母,而且字符串的長度固定,假設是L。那麼可以注意到每一個字符可以對應的邊有25個(26個小寫字母去掉自己),那麼一個字符串可能存在的邊是25*L條。接下來就是檢查這些對應的字符串是否在字典內,就可以得到一個完整的圖的結構。根據題目要求,等價於求這個圖中一個頂點到另一個頂點的最短路徑,我們一般用BFS廣度優先。

這道題,我們只能用最簡單的辦法去做,每次改變單詞的一個字母,然後逐漸搜索,這種求最短路徑,樹最小深度問題用BFS最合適。

和當前單詞相鄰的單詞,就是和頂點共邊的另一個頂點,是對當前單詞改變一個字母且在字典內存在的單詞。

找到一個單詞的相鄰單詞,加入BFS隊列後,我們要從字典內刪除,因為不刪除會造成類似hog->hot->hog這樣的死循環。而且刪除對求最短路徑沒有影響,因為我們第一次找到的單詞肯定是最短路徑,我們是層序遍歷去搜索的,最早找到的一定是最短路徑,即使後面的其他單詞也能轉換成它,路徑肯定不會比當前的路徑短。這道題僅要求求出最短路徑長度,不需要求輸出最短路徑,所以可以刪除這個單詞。

BFS隊列之間用空串”“來標示層與層的間隔,每次碰到層的結尾,遍歷深度+1,進入下一層。

三. 示例代碼

class Solution {
public:
    int ladderLength(string start, string end, unordered_set &dict) {
        if(start.size() == 0 || end.size() == 0) return 0;

        queue wordQ;
        wordQ.push(start);
        wordQ.push();
        int path = 1;

        while(!wordQ.empty())
        {
            string str = wordQ.front();
            wordQ.pop();

            if(str != )
            {
                int len = str.size();
                for(int i = 0; i < len; i++)
                {
                    char tmp = str[i];

                    for(char c = 'a'; c <= 'z'; c++)
                    {
                        if(c == tmp) continue;
                        str[i] = c;
                        if(str == end) return path + 1; //如果改變後的單詞等於end 返回path+1
                        if(dict.find(str) != dict.end())
                        {
                            wordQ.push(str);
                            dict.erase(str);   //字典內刪除這個詞 防止反復走
                        }
                    }
                    str[i] = tmp;  //重置回原來的單詞
                }
            }
            else if(!wordQ.empty())
            {
                //到達當前層的結尾,並且不是最後一層的結尾
                path++;
                wordQ.push();
            }
        }
        return 0;
    }
};

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved