問題

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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

例子

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

分析

注意到每個(gè)相鄰的單詞都只有一個(gè)字母的差異蟹但。我們可以使用bfs解決這個(gè)問題：從beginWord出發(fā)崎脉，每一層的單詞都和上一個(gè)單詞有一個(gè)字母的差別娜遵，不斷搜索乎澄，直到搜索到endWord。

要點(diǎn)

用two-side bfs算法可以加速O(logN/2)^M螃宙，N為單詞表個(gè)數(shù)蛮瞄，M為bfs樹節(jié)點(diǎn)的平均度數(shù)。因?yàn)閠wo-side bfs依次從beginWord和endWord開始遍歷谆扎，可以有效減少遍歷的次數(shù)挂捅。

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

代碼

bfs

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // unordered_set可以提高查找效率O(1)
        unordered_set<string> wordSet(wordList.begin(), wordList.end());

        queue<string> wordQueue;
        transform(beginWord, wordSet, wordQueue);

        int count = 2;
        while (!wordQueue.empty()) {
            int num = wordQueue.size();
            for (int i = 0; i < num; i++) {
                string word = wordQueue.front();
                wordQueue.pop();
                if (word == endWord) return count;
                transform(word, wordSet, wordQueue);
            }
            count++;
        }

        return 0;
    }

private:
    // 找出所有和word有一個(gè)字母不同的單詞，從單詞表里刪除堂湖，并且添加到隊(duì)列中
    void transform(string word, unordered_set<string> &wordSet, queue<string> &wordQueue) {
        for (int i = 0; i < word.size(); i++) {
            char letter = word[i];
            for (int j = 0; j < 26; j++) {
                word[i] = 'a' + j;
                if (wordSet.find(word) == wordSet.end()) continue;

                wordQueue.push(word);
                wordSet.erase(word);
            }
            word[i] = letter;
        }
    }
};

two-side bfs

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        wordSet.erase(beginWord);
        wordSet.erase(endWord);
        unordered_set<string> beginSet, endSet, *p1, *p2;
        beginSet.insert(beginWord);
        endSet.insert(endWord);
        p1 = &beginSet;
        p2 = &endSet;

        int ladder = 2;
        while (!p1->empty() && !p2->empty())
        {
            // 保持p1的大小小于p2闲先，提高遍歷效率
            if (p1->size() > p2->size())
                swap(p1, p2);

            unordered_set<string> tempSet;
            for (string word : *p1) {
                for (int i = 0; i < word.size(); i++) {
                    char letter = word[i];
                    for (int j = 0; j < 26; j++) {
                        word[i] = 'a' + j;
                        if (p2->find(word) != p2->end())
                            return ladder;
                        if (wordSet.find(word) != wordSet.end()) {
                            wordSet.erase(word);
                            tempSet.insert(word);
                        }
                    }
                    word[i] = letter;
                }
            }
            swap(*p1, tempSet);
            ladder++;
        }
        return 0;
    }
};