127_单词接龙.md

127.单词接龙

问题

给定两个单词（beginWord和 endWord）和一个字典，找到从beginWord 到endWord 的最短转换序列的长度。转换需遵循如下规则：

• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例`1:
输入:
beginWord = ";hit";,
endWord = ";cog";,
wordList = [";hot";,";dot";,";dog";,";lot";,";log";,";cog";]
输出: 5
解释: 一个最短转换序列是 ";hit"; -> ";hot"; -> ";dot"; -> ";dog"; -> ";cog";,
     返回它的长度 5。

示例 2:
输入:
beginWord = ";hit";
endWord = ";cog";
wordList = [";hot";,";dot";,";dog";,";lot";,";log";]
输出:`0
解释:`endWord ";cog"; 不在字典中，所以无法进行转换。

解答

最开始的朴素解法，用队列实现的BFS：

class Solution {
public:
    bool canChange(const string &a, const string &b) {
        int diff = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) {
                if (diff == 1) {
                    return false;
                }
                ++diff;
            }
        }
        return diff == 1;
    }

    int ladderLength(string begin, string end, vector<string>& wordList) {
        if (find(wordList.begin(), wordList.end(), end) == wordList.end()) {
            return 0;
        }

        int result = 0;
        queue<string> next;
        next.push(begin);
        unordered_set<string> words(wordList.begin(), wordList.end());
        vector<bool> visited (wordList.size(), false);

        while (!next.empty()) {
            queue<string> q;
            int len = next.size();
            for (int i = 0; i < len; ++i) {
                string w = next.front();
                next.pop();
                for (int i = 0; i < wordList.size(); ++i) {
                    if (visited[i]) {
                        continue;
                    }
                    auto x = wordList[i];
                    if (canChange(w, x)) {
                        if (x == end) {
                            return result + 2;
                        }
                        next.push(x);
                        visited[i] = true;
                    }
                }
            }
            ++result;
        }
        return 0;
    }
};

但是上面这个太慢了，瓶颈就在于做了很多无用功，而且比较两个字符串能否相互转换十分耗时。有一个比较好的解法，就是我们维护三个集合，分别是begin，end和words。当我们处理过一个字符串后，这个字符串再遇到就没有意义了，所以words就是起到这样的作用。然后begin表示我们已经搜索到的字符串，end是我们的目标。然后，我们对于每个word，都通过对每个位置修改为每个小写字母来构造可以转换的字符串，如果这个字符串在words中，就可以加入到下一层的begin(temp)中。然后，比较关键的是，如果begin的大小大于end了，就将两个交换一下，这样可以保证我们搜索的种子相对比较少，大大缩减了搜索次数。

class Solution {
public:

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) {
            return 0;
        }

        int result = 1, len = beginWord.size();
        unordered_set<string> begin = {beginWord}, end = {endWord};
        unordered_set<string> words(wordList.begin(), wordList.end());
        
        while (!begin.empty() && !end.empty()) {
            unordered_set<string> temp;
            ++result;

            if (begin.size() > end.size()) {
                swap(begin, end);
            }
            for (auto x : begin) {
                for (int i = 0; i < len; ++i) {
                    string word = x;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (word[i] == c) {
                            continue;
                        } else {
                            word[i] = c;
                        }
                        if (end.count(word)) {
                            return result;
                        }
                        if (words.count(word)) {
                            temp.insert(word);
                            words.erase(word);
                        }
                    }
                }
            }
            swap(begin, temp);
        }
        return 0;
    }
};