Word Ladder II: BFS
5 min readJul 25, 2021
For this problem, we can build the graph in two ways:
- Graph A: Check all posible pair of string to see whether they have distance of 1 and build the graph.
- Graph B: Change one character of the word to a new word and check whether the new word in unexplored word list.
Backtracking Graph A got TLE
class Solution {
public:
string end;
int len = INT_MAX;
bool disOne(string a, string b){
int cnt = 0;
for (int i = 0; i < a.size(); ++i){
cnt += a[i] != b[i];
if (cnt > 1) return false;
}
return cnt == 1;
}
void backtrack(string curr, unordered_map<string, vector<string>> &graph, vector<string> history, vector<vector<string>>& ret, unordered_set<string>& seen){
history.push_back(curr);
if (curr == end){
ret.push_back(history);
len = min(len, (int)history.size());
return;
}
if (history.size() >= len)return;
for (auto w: graph[curr]){
if (seen.find(w) == seen.end()) {
seen.insert(w);
backtrack(w, graph, history, ret, seen);
seen.erase(w);
}
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
const int n = wordList.size();
end = endWord;
// build graph
unordered_map<string, vector<string>> graph;
for (int i = 0; i < n - 1; ++i){
for (int j = i + 1; j < n; ++j){
if (disOne(wordList[i], wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
}
auto it = find(wordList.begin(), wordList.end(), beginWord);
if (it == wordList.end()){
for (auto word: wordList) if (disOne(beginWord, word))graph[beginWord].push_back(word);
}
vector<vector<string>> ret;
string curr = beginWord;
vector<string> history;
unordered_set<string> seen;
seen.insert(beginWord);
backtrack(curr, graph, history, ret, seen);
sort(ret.begin(), ret.end(), [](vector<string> &a, vector<string> &b){
return a.size() < b.size();
});
if (ret.empty()) return ret;
int minSz = (*ret.begin()).size();
vector<vector<string>> finret;
for (auto r: ret){
if (r.size() == minSz) finret.push_back(r);
}
return finret;
}
};Naive BFS graph A got AC (graph A)
class Solution {
public:
string end;
int len = INT_MAX;
bool disOne(string a, string b){
int cnt = 0;
for (int i = 0; i < a.size(); ++i){
cnt += a[i] != b[i];
if (cnt > 1) return false;
}
return cnt == 1;
}
void bfs(string curr, unordered_map<string, vector<string>> &graph, vector<vector<string>>& ret, unordered_set<string> seen){
vector<vector<string>> currentlevel;
currentlevel.push_back(vector<string>{curr});
bool found = false;
unordered_set<string> newseen;
while (currentlevel.size() && !found){
vector< vector<string>> nextlevel;
newseen = seen;
for (auto& vec: currentlevel){
for (auto s: graph[vec.back()]){
vector<string> thisvec = vec;
if (seen.find(s) == seen.end() || s == end){
newseen.insert(s);
thisvec.push_back(s);
if (s == end) {
found = true;
ret.push_back(thisvec);
continue;
}
nextlevel.push_back(thisvec);
}
}
}
currentlevel = nextlevel;
seen = newseen;
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<vector<string>> ret;
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return ret;
const int n = wordList.size();
end = endWord;
// build graph
unordered_map<string, vector<string>> graph;
for (int i = 0; i < n - 1; ++i){
for (int j = i + 1; j < n; ++j){
if (disOne(wordList[i], wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
}
auto it = find(wordList.begin(), wordList.end(), beginWord);
if (it == wordList.end()){
for (auto word: wordList) if (disOne(beginWord, word))graph[beginWord].push_back(word);
}
unordered_set<string> seen;
seen.insert(beginWord);
bfs(beginWord, graph, ret, seen);
return ret;
}
};runtime
Runtime: 36 ms, faster than 23.18% of C++ online submissions for Word Ladder II.Memory Usage: 19.8 MB, less than 10.99% of C++ online submissions for Word Ladder II.
BFS by changing the graph from string to int, got AC (graph A)
class Solution {
public:
string end;
//int len = INT_MAX;
vector<string> wordList;
bool disOne(int i, int j){
int cnt = 0;
//cout << wordList.size()<<endl;
auto a = wordList[i], b = wordList[j];
for (int k = 0; k < a.size(); ++k){
cnt += a[k] != b[k];
if (cnt > 1) return false;
}
return cnt == 1;
}
void bfs(int curr, vector<vector<int>> &graph, vector<vector<int>>& ret, unordered_set<int> seen){
vector<vector<int>> currentlevel;
currentlevel.push_back(vector<int>{curr});
bool found = false;
unordered_set<int> newseen;
while (currentlevel.size() && !found){
vector< vector<int>> nextlevel;
newseen = seen;
for (auto& vec: currentlevel){
for (auto s: graph[vec.back()]){
vector<int> thisvec = vec;
if (seen.find(s) == seen.end() || wordList[s] == end){
newseen.insert(s);
thisvec.push_back(s);
if (wordList[s] == end) {
found = true;
ret.push_back(thisvec);
continue;
}
nextlevel.push_back(thisvec);
}
}
}
currentlevel = nextlevel;
seen = newseen;
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
const int n = wordList.size();
vector<vector<int>> ret;
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return {};
end = endWord;
int root = -1;
// build graph
wordList.push_back(beginWord);
this -> wordList = wordList;
vector<vector<int>> graph(n+1);
for (int i = 0; i < n - 1; ++i){
if (wordList[i] == beginWord) root = i;
for (int j = i + 1; j < n; ++j){
auto good = disOne(i, j);
if (good){
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
if (root == -1){
root = n;
for (int i =0; i < n; ++i) if (disOne(i, n))graph[n].push_back(i);
}
unordered_set<int> seen;
seen.insert(root);
bfs(root, graph, ret, seen);
vector<vector<string>> finret;
for (auto r: ret){
vector<string> thisone;
for (int i: r) thisone.push_back(wordList[i]);
finret.push_back(thisone);
}
return finret;
}
};runtime
Runtime: 32 ms, faster than 26.20% of C++ online submissions for Word Ladder II.Memory Usage: 11.3 MB, less than 39.62% of C++ online submissions for Word Ladder II.
Python BFS can get AC (graph B)
The following python code can get AC, the key idea is changing each character to construct a new word. Once the new word is in the unexplored word set, then explore this node. Seems this one is pretty fast.
class Solution:
def findLadders(self, begin: str, end: str, wordList: List[str]) -> List[List[str]]:
res = []
def bfs(begin):
word_set = set(wordList)
level = [(begin, begin)]
found = False
while level and not found:
new_level = []
for word, hist in level:
for i in range(len(word)):
for new_c in "abcdefghijklmnopqrstuvwxyz":
new_word = word[:i]+new_c+word[i+1:]
if new_word in word_set:
if new_word == end:
found = True
res.append(hist+","+new_word)
else:
new_level.append((new_word, hist+','+new_word))
word_set-={w for w, _ in new_level}
level = new_level
bfs(begin)
return [r.split(',') for r in res] if res else []Run time
Runtime: 88 ms, faster than 33.78% of Python3 online submissions forWord Ladder II.Memory Usage: 14.5 MB, less than 87.41% of Python3 online submissions for Word Ladder II.
C++ version (Graph B)
class Solution {
public:
string end;
void bfs(string word, unordered_set<string>& words,vector<vector<string>>& ret ){
vector<vector<string>> level;
if (words.find(end) == words.end())return;
level.push_back(vector<string>{word});
bool done = false;
while (!level.empty() && !done){
vector<vector<string>> newLevel;
unordered_set<string> seen;
for (auto vec: level){
string lastWord = vec.back();
for (int i = 0; i < lastWord.size(); ++i){
for (char c = 'a'; c <= 'z'; ++c){
if (c == lastWord[i]) continue;
string newWord = lastWord;
newWord[i] = c;
if (newWord == end){
done = true;
vector<string> newvec(vec.begin(), vec.end());
newvec.push_back(newWord);
ret.push_back(newvec);
continue;
}
if (words.find(newWord) != words.end()){
seen.insert(newWord);
vector<string> newvec = vec;
newvec.push_back(newWord);
newLevel.push_back(newvec);
}
}
}
}
for (auto w: seen) words.erase(w);
level = newLevel;
}}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
end = endWord;
unordered_set<string> words(wordList.begin(), wordList.end());
vector<vector<string>> ret;
bfs(beginWord, words, ret);
return ret;
}
};
Runtime
Runtime: 20 ms, faster than 44.90% of C++ online submissions for Word Ladder II.Memory Usage: 12.9 MB, less than 19.36% of C++ online submissions for Word Ladder II.
The complexity of this algorithm should be O(26*n*k) where n is the wordList size and k is the beginWord size. maximum n is 1000 and maximum k is 5. So the total complexity is O(26*1000*5) = O(130K)
