题解 | #牛群最短移动序列#

考察的知识点：哈希、广度优先搜索；

解答方法分析：

1. 创建一个无序集合dict，将单词列表wordList中的所有单词添加到其中，以便快速查找。
2. 创建一个队列q，并将开始单词beginWord放入队列中。
3. 创建一个无序集合visited，并将开始单词beginWord添加到其中表示已访问过。
4. 创建一个变量step，用于记录转换步骤。
5. 通过while循环，判断队列是否为空，如果不为空，则执行以下步骤：a. 获取当前队列中的单词数量size。b. 遍历size次，对当前队列中的单词进行处理：从队列中弹出一个单词curWord。如果curWord等于结束单词endWord，则返回步骤数step。对curWord的每个字符进行变换，将其替换为a到z的每个字符：保存替换前的原始字符originalChar。将curWord的第j个字符替换为字符c。如果dict中存在替换后的单词curWord，并且该单词未被访问过（即未在visited中），则将curWord添加到队列q中，并将其添加到visited中表示已访问过。恢复curWord的第j个字符为原始字符originalChar。c. 增加步骤数step。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param beginWord string字符串
     * @param endWord string字符串
     * @param wordList string字符串vector
     * @return int整型
     */
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> q;
        q.push(beginWord);
        unordered_set<string> visited;
        visited.insert(beginWord);
        int step = 1;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string curWord = q.front();
                q.pop();

                if (curWord == endWord) {
                    return step;
                }
                for (int j = 0; j < curWord.length(); j++) {
                    char originalChar = curWord[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        curWord[j] = c;
                        if (dict.find(curWord) != dict.end() &&
                                visited.find(curWord) == visited.end()) {
                            q.push(curWord);
                            visited.insert(curWord);
                        }
                    }
                    curWord[j] = originalChar;
                }
            }
            step++;
        }
        return 0;
    }
};