没做过这种图论的题目,一脸懵逼😳,看了大佬的解析,自己再总结(fushu)一遍:

将所有路径表示出来——

        ->lot->log
hit->hot          ->cog
        ->dot->dog

这个其实就是求图论中的单源最短路径,图中边是没有权重的,用BFS求解最合适(时间复杂度O(n))。

class Solution {
public:
    int ladderLength(string start, string end, unordered_set &dict) {
        queue> record;
        record.push(make_pair(start, 1));
        while (!record.empty()) {
            pair current = record.front();
            record.pop();
            if (current.first == end) {
                return current.second;
            }
            // 替换每一个字符,并在set中搜寻
            for (int i = 0; i < current.first.size(); ++i) {
                for (int j = 0; j < 26; ++j) {
                    string str = current.first;
                    str[i] = 'a' + j;
                    if (dict.find(str) != dict.end()) {
                        record.push(make_pair(str, current.second+1));
                        dict.erase(str);
                    }
                }
            }
        }
        return 0;
    }
};