LeetCode127—Word Ladder

原題

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;
    }
};