PlainText
class Solution {
struct kidnodeinfo{
int distance = 1412;
vector<int> all_source_nodes = vector<int>();
kidnodeinfo(){}
kidnodeinfo(int d, vector<int> v):distance(d),all_source_nodes(v){}
};
vector<vector<string>> result;
vector<string> templadder;
void getting_ladders(const kidnodeinfo*, const vector<string>&, const int&);
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
const int listlen = wordList.size();
//建立通配符字典,便于查看某个词的所有相邻词
unordered_map<string, vector<int>> worddict;
kidnodeinfo kidconnection[1412];//邻接表节点
int endlabel = -1, beginlabel = -1;
for(int wordlabel = 0; wordlabel < listlen; wordlabel++){
string& word = wordList[wordlabel];
endlabel = (word==endWord ? wordlabel : endlabel);
beginlabel = (word==beginWord ? wordlabel : beginlabel);
kidconnection[wordlabel]= kidnodeinfo();//顺手初始化邻接表节点
for(char& c:word){
char originc = c;
c = '*';
if(worddict.find(word)==worddict.end())worddict[word] = vector<int>();
vector<int>& targetdict = worddict[word];
c = originc;
targetdict.push_back(wordlabel);
}
}
if(endlabel==-1)return result;
else kidconnection[endlabel] = kidnodeinfo(0, {endlabel});
bool pushed = false;
if(beginlabel == -1){
pushed = true;
beginlabel = listlen;
wordList.push_back(beginWord);
kidconnection[listlen] = kidnodeinfo();
for(char& c:beginWord){
char originc = c;
c = '*';
if(worddict.find(beginWord)==worddict.end())worddict[beginWord] = vector<int>();
vector<int>& targetdict = worddict[beginWord];
c = originc;
targetdict.push_back(listlen);
}
}
//邻接表各个节点已经顺手初始化,接下来直接更新邻接表节点
vector<int> scannode = {endlabel}, nextscan = {};
while(!scannode.empty()){
//扫描本次要更新的节点
for(const int& scanlabel:scannode){
string& scan = wordList[scanlabel];
//遍历该节点的所有通配符
for(char& c:scan){
char originc = c;
c = '*';
//该通配符下所有节点就是与其相邻的节点,注意除掉它自己
const vector<int>& adjacent_labels = worddict[scan];
c = originc;
const kidnodeinfo& scaninfo = kidconnection[scanlabel];
for(const int& ad_label:adjacent_labels){
kidnodeinfo& nextinfo = kidconnection[ad_label];
if(nextinfo.distance == 1412){
nextinfo.distance = scaninfo.distance+1;
nextscan.push_back(ad_label);
nextinfo.all_source_nodes.push_back(scanlabel);
}
else if(nextinfo.distance == scaninfo.distance+1){
nextinfo.all_source_nodes.push_back(scanlabel);
}
}
}
}
swap(scannode, nextscan);
nextscan.clear();
}
//获取所有路径
getting_ladders(kidconnection, wordList, beginlabel);
if(pushed)wordList.pop_back();
return result;
}
};
void Solution::getting_ladders(const kidnodeinfo* connection, const vector<string>& wordlist, const int& nowlabel){
templadder.push_back(wordlist[nowlabel]);
if(connection[nowlabel].distance == 0){
result.push_back(templadder);
}
else{
for(const int& nextnode:connection[nowlabel].all_source_nodes){
getting_ladders(connection, wordlist, nextnode);
}
}
templadder.pop_back();
}
评论 (0)


