Word Ladder

解题思路

  1. 一个重要的能力就是将具体的问题抽象为已知的知识结构中。这道题需要仔细思考，其实就是一道 BFS 问题。

  2. 明白了是 BFS，具体代码上也会产生巨大的性能差异，下面列出我一开始写的性能较差的版本和性能很好的版本。

代码

// Slow Solution
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, bool> wordMap;
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        for (auto word : wordList) {
            wordMap[word] = (word==beginWord)? false: true;
        }
        vector<string> bfs;
        bfs.push_back(beginWord);
        int res = 1;
        while (!bfs.empty()) {
            res++;
            vector<string> temp;
            for (auto word : bfs) {
                for (auto it = wordMap.begin(); it != wordMap.end(); ++it) {
                    if (it->second == true && isNext(word, it->first)) {
                        if (it->first == endWord) {
                            return res;
                        }
                        temp.push_back(it->first);
                        it->second = false;
                    }
                }
            }
            swap(bfs, temp);
        }
        return 0;
    }
    
    bool isNext(const string& word1, const string& word2) {
        int distance = 0;
        for (int i = 0; i < word1.size(); ++i) {
            if (word1[i] != word2[i] && ++distance > 1) {
                return false;
            }
        }
        return (distance == 1) ? true: false;
    }
};

// Fast Solution
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> start{beginWord};
        unordered_set<string> end{endWord};
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) {
            return 0;
        }
        int step = 1;
        while (!start.empty() && !end.empty()) {
            step++;
            unordered_set<string> temp;
            if (start.size() > end.size()) {
                swap(start, end);
            }
            for (auto w : start) {
                for (int i = 0; i < w.size(); ++i) {
                    string word = w;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == word[i]) {
                            continue;
                        } else {
                            word[i] = c;
                        }
                        if (end.count(word)) {
                            return step;
                        }
                        if (wordSet.count(word)) {
                            temp.insert(word);
                            wordSet.erase(word);
                        }
                    }
                }
            }
            swap(start, temp);
        }
        return 0;
    }
};