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

LeetCode127—Word Ladder

編輯:關於C++

原題

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“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.


分析1

要把這題轉化成圖論的問題,下述思路構建圖:

1.beginWord、endWord、wordList裡面的詞作為圖中的節點。
2.以確定這些節點是否可達:如果變換一個字符能夠到另一個單詞則說明可達
3.對圖進行廣度優先搜索,找出起點到終點的長度。

問題

這是我最開始的思路,並且實現了,但是遇到了一個問題,就是 當wordList中單詞太多則圖的規模就會變得很大,最終就會超時(Time Limit Exceeded),這裡也貼出超時代碼吧:

class Solution {
private:
    bool isConnect(const string &a, const string&b)
    {//判斷兩個單詞是否可達關系
        int count = 0;
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] != b[i])
                count++;
            if (count > 1)
                return false; 
        }
        if (count == 1)//只有一個字符不同
            return true;
        else
            return false;
    }
    void buildMap(vector>&wordMap, mapwordTable)
    {
        int mapSize = wordTable.size();
        for (auto it1 = wordTable.begin(); it1 != wordTable.end(); it1++)
        {
            for (auto it2 = it1; it2 != wordTable.end(); it2++)
            {
                if (isConnect(it1->first, it2->first))
                {
                //初始化鄰接矩陣(1-可達 0-不可達)
                    wordMap[it1->second][it2->second] = 1;
                    wordMap[it2->second][it1->second] = 1;
                }
            }
        }
    }
    int BFS(vector>&wordMap, string start, string end, mapwordTable)
    {
        vectorvisit(wordTable.size(), false);//訪問表
        queueq;
        queued;//記錄距離distance的輔助隊列
        q.push(wordTable[start]);
        d.push(1);
        visit[wordTable[start]] = true;
        while (!q.empty())
        {
            int t = d.front();
            int i = q.front();
            d.pop();
            q.pop();
            if (i == wordTable[end])//找到終點
            {
                return t;
            }
            for (int j = 0; j < wordMap.size(); j++)
            {
                if (!visit[j] && wordMap[i][j] == 1)
                {
                    visit[j] = true;
                    q.push(j);
                    d.push(t + 1);
                }
            }
        }//end while
        return 0;
    }
public:
    int ladderLength(string beginWord, string endWord, unordered_set& wordList) {
        mapwordTable;//單詞索引表
        wordTable[beginWord] = 0;
        wordTable[endWord] = 1;
        auto it = wordList.begin();
        int index = 2;
        for (; it != wordList.end(); it++)//
        {
            if (wordTable.find(*it)==wordTable.end())
                wordTable[*it] = index++;//建立一個單詞-索引表方便建圖
        }
        int size = wordTable.size();
        vector> wordMap(size,vector(size,0));//初始化鄰接矩陣
        buildMap(wordMap, wordTable);//建圖
        return BFS(wordMap, beginWord, endWord, wordTable);
        //return 0;
    }
};

分析2

其實不用把整個圖建出來,可以走一步看一步,也就是說:

當訪問到節點A時,可以先求出所有跟節點A臨接且未被訪問的節點入隊,然後按照BFS的思路做即可。

但是,修改後的代碼依然是超時,後來找原因發現是我在“判斷兩個節點是否臨接”這個步驟中使用的算法效率太低,對比網上的思路:

我的方法是:把當前節點的單詞current和wordList裡面的所有詞比較,不相同的字符的個數為1的時候return true,否則return false。這樣做的缺點是,不論如何都要遍歷完整個wordList,查找時間復雜度是O(n)

網上一種思路是:替換當前節點的單詞current每個字符(從a~z),然後看看替換過後的單詞是否在單詞表中,這裡我不理解的是,由於我們是用unordered_set來保存單詞表,雖然最壞情況下的時間復雜度會到O(n),但一般情況下是可以在常數時間O(1)下訪問的,因此使用unordered_set::find的時間復雜度是要低於線性時間復雜度的,這樣就提高了效率。


代碼

class Solution {
private:
    void buildMap(string end,vector&connect,unordered_set&visit,string& current,const unordered_set&wordList)
    {
        connect.clear();
        string cur = current;
        /*
        超時:時間復雜度O(n)
        for(auto i=wordList.begin();i!=wordList.end();i++)
        {
            if(visit.find(*i)!=visit.end())
                continue;
            if(isConnect(cur,*i))
                connect.push_back(*i);
        }
        */

        #if 1
        for (int i = 0; i < cur.size(); i++)
        {
            char t = cur[i];
            for (char c = 'a'; c < 'z'; c++)
            {
                if (c == t)
                {
                    continue;
                }
                cur[i] = c;
                if ((cur == end || wordList.find(cur) != wordList.end()) && (visit.find(cur) == visit.end()))
                {
                    connect.push_back(cur);
                }
            }
            cur[i]=t;
        }
        #endif
    }
    int BFS(string beginWord, string endWord, unordered_set& wordList)
    {
        queueq;
        queued;//路徑distance的輔助隊列
        unordered_setvisit;
        vectorconnect;
        q.push(beginWord);
        d.push(1);
        while (!q.empty())
        {
            string current = q.front();
            int tmpDist = d.front();
            q.pop();
            d.pop();
            buildMap(endWord,connect, visit, current, wordList);//獲取臨接單詞
            if (current == endWord)//找到終點
            {
                return tmpDist;
            }
            for (int i = 0; i < connect.size(); i++)
            {
                if (visit.find(connect[i]) == visit.end())//未被訪問
                {
                    visit.insert(connect[i]);
                    q.push(connect[i]);
                    d.push(tmpDist + 1);
                }
            }
        }
        return 0;//沒有找到路徑
    }

public:
    int ladderLength(string beginWord, string endWord, unordered_set& wordList) {
        int res= BFS(beginWord, endWord, wordList);
        return res;
    }
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved