Using BFS to solve a hard problem

Explanation

This is a hard problem in leetcode which can be solved by the BFS. Usually the BFS can be used to find the shortest path problem and most case only the cost of the path should be returned. For this problem, all shortest path should be found. Based on this, we need extra trick on maintaining the seen set. The basic idea is:

  • Keep a seen for all previous levels.
  • For the current level, maintain a temp seen and this temp seen will not influence the exploration of current level (one node may be visited multiple times from different paths where they have the same depth, for example: ABE; CDE)
  • After traversing the current level, add the temp seen to the seen.

Based on this, key steps will be

  • Build the graph
  • BFS with specially designed seen.

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;
}
};

Run time

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

[1]https://jimmy-shen.medium.com/word-ladder-ii-bfs-7ec9f2b0a29b

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store