A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
- Every adjacent pair of words differs by a single letter.
- Every
si
for1 <= i <= k
is inwordList
. Note thatbeginWord
does not need to be inwordList
. sk == endWord
Given two words,beginWord
andendWord
, and a dictionarywordList
, return the number of words in the shortest transformation sequence frombeginWord
toendWord
, or 0 if no such sequence exists.
Solution
注意到每次只能变一个字符,所以我们可以遍历每一个位置,将其设置为 \(\#\),然后用 \(map\) 映射到 \(string\) 的 \(vector\) 里面。所以我们就可以利用 \(BFS\) 的方式,其中队列里面存储 \(pair(str, step)\)
点击查看代码
class Solution {
private:
unordered_map<string, vector<string>> mp;
queue<pair<string, int>> q;
unordered_map<string,int> vis;
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if(count(wordList.begin(), wordList.end(), endWord)==0)
return 0;
int n = wordList.size();
wordList.push_back(beginWord);
int m = wordList[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
string tmp = wordList[i].substr(0,j)+'#'+wordList[i].substr(j+1,m-j-1);
mp[tmp].push_back(wordList[i]);
}
}
q.push({beginWord, 1});
while(!q.empty()){
auto f = q.front();q.pop();
vis[f.first]=1;
string cur = f.first;
int cur_step = f.second;
for(int i=0;i<m;i++){
string tmp = cur.substr(0,i)+'#'+cur.substr(i+1,m-i-1);
for(auto t:mp[tmp]){
if(!vis[t]){
if(t==endWord)return cur_step+1;
q.push({t, cur_step+1});
}
}
}
}
return 0;
}
};