# 88ms! Accepted c++ solution with two-end BFS. 68ms for Word Ladder and 88ms for Word Ladder II

• In order to reduce the running time, we should use two-end BFS to slove the problem.

Accepted 68ms c++ solution for Word Ladder.

``````class Solution {
public:
int ladderLength(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
if (beginWord == endWord)
return 1;
std::unordered_set<std::string> words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
dict.erase(beginWord);
dict.erase(endWord);
}

private:
int ladderLengthHelper(std::unordered_set<std::string> &words1, std::unordered_set<std::string> &words2, std::unordered_set<std::string> &dict, int level) {
if (words1.empty())
return 0;
if (words1.size() > words2.size())
std::unordered_set<std::string> words3;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = *it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = *ch;
for (*ch = 'a'; *ch <= 'z'; ++(*ch))
if (*ch != tmp)
if (words2.find(word) != words2.end())
return level + 1;
else if (dict.find(word) != dict.end()) {
dict.erase(word);
words3.insert(word);
}
*ch = tmp;
}
}
return ladderLengthHelper(words2, words3, dict, level + 1);
}
};
``````

Accepted 88ms c++ solution for Word Ladder II.

``````class Solution {
public:
std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
std::vector<std::vector<std::string> > paths;
std::vector<std::string> path(1, beginWord);
if (beginWord == endWord) {
paths.push_back(path);
return paths;
}
std::unordered_set<std::string> words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
std::unordered_map<std::string, std::vector<std::string> > nexts;
bool words1IsBegin = false;
if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
getPath(beginWord, endWord, nexts, path, paths);
return paths;
}
private:
std::unordered_set<std::string> &words1,
std::unordered_set<std::string> &words2,
std::unordered_set<std::string> &dict,
std::unordered_map<std::string, std::vector<std::string> > &nexts,
bool &words1IsBegin) {
words1IsBegin = !words1IsBegin;
if (words1.empty())
return false;
if (words1.size() > words2.size())
return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
for (auto it = words1.begin(); it != words1.end(); ++it)
dict.erase(*it);
for (auto it = words2.begin(); it != words2.end(); ++it)
dict.erase(*it);
std::unordered_set<std::string> words3;
bool reach = false;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = *it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = *ch;
for (*ch = 'a'; *ch <= 'z'; ++(*ch))
if (*ch != tmp)
if (words2.find(word) != words2.end()) {
reach = true;
words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
}
else if (!reach && dict.find(word) != dict.end()) {
words3.insert(word);
words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
}
*ch = tmp;
}
}
return reach || findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
}
void getPath(
std::string beginWord,
std::string &endWord,
std::unordered_map<std::string, std::vector<std::string> > &nexts,
std::vector<std::string> &path,
std::vector<std::vector<std::string> > &paths) {
if (beginWord == endWord)
paths.push_back(path);
else
for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
path.push_back(*it);
getPath(*it, endWord, nexts, path, paths);
path.pop_back();
}
}
};
``````

• `if (*ch != tmp)` is unnecessary since you have erased that word in `dict`.

• Hi, prime_tang. Thanks for your two-end BFS code. It is really fast!

I have rewritten your code below. I hope it is Ok.

``````class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
unordered_set<string> startWords, endWords;
startWords.insert(start);
endWords.insert(end);
unordered_map<string, vector<string> > children;
bool flip = true;
if (searchLadders(startWords, endWords, dict, children, flip))
}
private:
unordered_set<string>& dict, unordered_map<string, vector<string> >& children, bool flip) {
flip = !flip;
if (startWords.empty()) return false;
if (startWords.size() > endWords.size())
return searchLadders(endWords, startWords, dict, children, flip);
for (string word : startWords) dict.erase(word);
for (string word : endWords) dict.erase(word);
unordered_set<string> intermediate;
bool done = false;
for (string word : startWords) {
int n = word.length();
string temp = word;
for (int p = 0; p < n; p++) {
char letter = word[p];
for (int i = 0; i < 26; i++) {
word[p] = 'a' + i;
if (endWords.find(word) != endWords.end()) {
done = true;
flip ? children[word].push_back(temp) : children[temp].push_back(word);
}
else if (!done && dict.find(word) != dict.end()) {
intermediate.insert(word);
flip ? children[word].push_back(temp) : children[temp].push_back(word);
}
}
word[p] = letter;
}
}
return done || searchLadders(endWords, intermediate, dict, children, flip);
}
void genLadders(string& start, string& end, unordered_map<string, vector<string> >& children,
if (start == end) {
return;
}
for (string child : children[start]) {
}
}
};``````

• Hi, jianchao.li.fighter, thanks!

• Thanks for your reminder that `if (*ch != tmp)` is unnecessary !

• Hi, prime_tang. Your code is really fast! :-)

• explain your ideas than just copy pasting

• The logic of this problem is not complicated, I think we can try to read the code and understand it by oneself. Therefore, I did not provide detailed explanation, but noted that it is a two-end BFS solution. Happy try! Just like `jianchao.li.fighter` does!

• I found a better cleaner solution

• I rewrite it so no recursion is needed!

``````bool buildNexts(string start, string end, unordered_set<string> &dict, map<string,vector<string>> &nexts) {
int len = start.size();
bool headIsFront = true, found = false;
}
unordered_set<string> tmp;
dict.erase(word);
for (int i = 0;i < len;++i) {
char letter = word[i];
for (int j = 'a';j <= 'z';++j) {
word[i] = j;
if (tail.find(word) != tail.end()) {
found = true;
} else if (!found && dict.find(word) != dict.end()) {
tmp.insert(word);
}
}
word[i] = letter;
}
}
if (found) return true;
for (auto word: tmp) // it's important to delete words here, but no other places!
dict.erase(word);
}
return false;
}

void buildAns(string start, string end, map<string,vector<string>> &nexts, vector<string> &path, vector<vector<string>> &ans) {
if (start == end) {
ans.push_back(path);
return;
}
for (auto s :nexts[start]) {
path.push_back(s);
buildAns(s, end, nexts, path, ans);
path.pop_back();
}
}

vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
vector<vector<string>> ans;
vector<string> path(1, start);;
map<string,vector<string>> nexts;
if (buildNexts(start,end,dict,nexts))
buildAns(start,end,nexts,path,ans);
return ans;
}``````

• Is there any way that don't need to change dictionary?

• What are you checking with `bool words1IsBegin`?

• I find some tricky place.In fact this solution uses some feature of compiler, because if you reverse the order of "return done || searchLadders(endWords, intermediate, dict, children, flip);" into "return searchLadders(endWords, intermediate, dict, children, flip) || done;", it will generate some extra "correct" but longer path, which don't satisfy the "shortest path" request of the problem.
I think using this compiler's feature to avoid unnecessary further recursion is so clever! Thanks for sharing, code for fun ;)

• @JulianWang12 That's simply because `||` will shortcut the right hand side if the left hand side is already `true`.

• Why we are using flip variable ?

• Actually, the "dict.erase(word);" after for is not needed,it will be executed only twice in the process, just earse beginword and endword

• Hi Jianchao,

May I ask how your algo handles the "collision" case, which means that at one level, 2 words will grow the the same word in the next level, like "mark" and "part" both go to "park" in the next level?

In this case, doesn't the "part" have 2 paths?

When I tackled this question, I used an unordered_map<string, vector<list<string))) (cpp) to store the paths. It beats 70% of answers, but still not concise enough.