LeetCode 127. 单词接龙
原题链接
困难
作者:
我是java同学
,
2023-08-11 14:47:47
,
所有人可见
,
阅读 70
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> S(wordList.begin(), wordList.end());
unordered_map<string, int> dist;//可能一个单词有多条路径,多个dist,所以要去重
dist[beginWord] = 0;
queue<string> q;
q.push(beginWord);
while (q.size()) {
auto t = q.front();
q.pop();
string r = t;
for (int i = 0; i < t.size(); i ++ ) {
t = r;
for (char j = 'a'; j <= 'z'; j ++ ) {
t[i] = j;
if (S.count(t) && !dist.count(t)) {
dist[t] = dist[r] + 1;
if (t == endWord) return dist[t] + 1;
q.push(t);
}
}
}
}
return dist[endWord];
}
};