大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题主要考察图的最短路径算法，我们可以使用广度优先搜索（BFS）来解决这个问题。

题目解答方法的文字分析

我们可以将每个牛编号看作图中的一个节点，如果两个牛编号只有一个字母不同，那么它们之间就有一条边。然后，我们可以以beginWord为起点，使用BFS找到到达endWord的最短路径，路径上的每个节点表示改变一个字母后的一个编号。

具体步骤如下：

  1. 将beginWord加入队列，表示起点。
  2. 创建一个set，用于记录已经访问过的节点，将beginWord加入set中。
  3. 使用BFS遍历图，直到队列为空。
  4. 在BFS遍历中，从队列中取出一个节点，表示当前位置的牛编号。
  5. 将当前节点的每个字母逐个替换为'a'~'z'，并在wordList中查找是否有这个新的编号。
  6. 如果找到了新的编号且未被访问过，则将新的编号加入队列，并将其与当前节点建立边。
  7. 如果找到了endWord，表示已经找到了最短路径，直接返回路径长度。

本题解析所用的编程语言 (C++)

C++

完整且正确的编程代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end()); // 将wordList转换为set，用于快速查找
        if (!dict.count(endWord)) {
            return 0; // endWord不在字典中，无法到达
        }
        
        queue<string> q;
        q.push(beginWord);
        unordered_set<string> visited; // 记录已经访问过的节点
        visited.insert(beginWord);
        
        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            steps++;
            
            for (int i = 0; i < size; i++) {
                string curr = q.front();
                q.pop();
                
                // 将当前节点的每个字母逐个替换为'a'~'z'，并查找是否有这个新的编号
                for (int j = 0; j < curr.length(); j++) {
                    char orig_char = curr[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig_char) {
                            continue;
                        }
                        
                        curr[j] = c;
                        if (curr == endWord) {
                            return steps + 1; // 找到了endWord，返回路径长度
                        }
                        
                        if (dict.count(curr) && !visited.count(curr)) {
                            q.push(curr);
                            visited.insert(curr);
                        }
                    }
                    curr[j] = orig_char; // 恢复原始状态
                }
            }
        }
        
        return 0; // 没有找到最短路径
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！