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

考察知识点：哈希、层序遍历

题目分析：

首先要自己举几个例子，发现其中的规律。

发现beginWord在选择要更改的字符的时候，不一定是先改第一个字符，或者是将第一个字符改成endWord第一个字符，这样都是没有观察例子，盲目猜测的结果。

通过观察例子，我们发现，与beginWord只有一个字符之差的所有字符串都应该访问一遍，子树同理。那么我们就可以将问题转化为层序遍历，找最短的路径即可。

所用编程语言：C++

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

                for (int j = 0; j < curr.length(); j++) {
                    char orig = curr[j];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == orig) continue;
                        curr[j] = ch;
                        if (st.count(curr)) {
                            if (curr == endWord) return steps + 1;
                            if (!visited.count(curr)) {
                                q.push(curr);
                                visited.insert(curr);
                            }
                        }
                    }
                    curr[j] = orig;
                }
            }
        }
        return 0;
    }
};