Using BFS to solve a hard problem

Explanation

Reference Code

class Solution {
public:
vector<string> words;
int dis(int i, int j){
int ret = 0;
for (int k = 0; k < words[i].size(); ++k){
ret += words[i][k] != words[j][k];
}
return ret;
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
wordList.push_back(beginWord);
unordered_set<string> s(wordList.begin(), wordList.end());
if (s.find(endWord) == s.end()) return {};
vector<string> words(s.begin(), s.end());
unordered_map<string, vector<string>> graph;
const int n = words.size();
this -> words = words;
// Build graph
for (int i = 0; i < n - 1; ++i){
for (int j = i + 1; j < n; ++j){
if (dis(i, j) == 1){
graph[words[i]].push_back(words[j]);
graph[words[j]].push_back(words[i]);
}
}
}
vector<vector<string>> ret;
// BFS
int shortestLevel = INT_MAX;
vector<vector<string>> currentLevel;
currentLevel.push_back({beginWord});
int level = 1;
unordered_set<string> seen;
seen.insert(beginWord);
while (!currentLevel.empty()){
vector<vector<string>> newLevel;
// keep a this seen for this level and add those seen members after the traverse of this level as we may visit the same element multiple times only if they are on the same level.
unordered_set<string> thisseen;
for (auto words: currentLevel){
for (auto nei: graph[words.back()]){
vector<string> newWords = words;
if (seen.find(nei) != seen.end()) {
continue;
}
if (nei == endWord && level + 1 <= shortestLevel){
newWords.push_back(nei);
ret.push_back(newWords);
shortestLevel = level + 1;
} else if (nei != endWord && level + 1 < shortestLevel){
newWords.push_back(nei);
newLevel.push_back(newWords);
thisseen.insert(nei);
}
}
}
for (auto word: thisseen) seen.insert(word);
level++;
currentLevel = newLevel;
}
return ret;
}
};
Runtime: 84 ms, faster than 13.20% of C++ online submissions for Word Ladder II.Memory Usage: 20.9 MB, less than 14.77% of C++ online submissions for Word Ladder II.

Reference

Data Scientist/MLE/SWE @takemobi