没做过这种图论的题目,一脸懵逼😳,看了大佬的解析,自己再总结(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; } };