# 127ms C++ Solution

• Anyone who has suggestions for further optimization?

``````class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
unordered_map<string, vector<vector<string>>> set1, set2, *set_cur, *set_target;
vector<vector<string>> vec_start(1, vector<string>(1, start)), vec_end(1, vector<string>(1, end));
//two-end BFS to effectively prune, BFS strategy will get the smaller set to traverse in each iteration
set1[start] = vec_start;
set2[end] = vec_end;
int K = start.size();
bool isUpdated = true, isFinished = false;
vector<vector<string>> res;
for(int depth = 2; isUpdated && !isFinished; ++depth) {
if(set1.size() > set2.size()) {
set_cur = &set2;
set_target = &set1;
}
else {
set_cur = &set1;
set_target = &set2;
}
unordered_map<string, vector<vector<string>>> inter_set;
isUpdated = false;
unordered_set<string> deleting;
for(auto iteri=set_cur->cbegin(), end = set_cur->cend(); iteri!=end; ++iteri) {
for(int i=0; i<K; ++i) {
string temp = (*iteri).first;
char ch = 'a';
for(int c = 0; c<26; ++c) {
temp[i] = ch + c;
if(set_target->find(temp) != set_target->end()) {
const vector<vector<string>> *new_paths_first = &(*iteri).second;
const vector<vector<string>> *new_paths_second = &(*set_target)[temp];
auto iter_in = set_cur->cbegin();
if(((*iter_in).second)[0][0] != start) {
new_paths_first = &(*set_target)[temp];
new_paths_second = &(*iteri).second;
}
for_each(new_paths_first->cbegin(), new_paths_first->end(), [&] (const vector<string> &first_path) {
for_each(new_paths_second->cbegin(), new_paths_second->cend(), [&] (const vector<string> &second_path) {
vector<string> temp_path = first_path;
for_each(second_path.crbegin(), second_path.crend(), [&](const string &s) {
temp_path.push_back(s);
});
res.push_back(temp_path);
});
});
isFinished = true;
}
else if(dict.find(temp) != dict.end()) {
vector<vector<string>> new_paths = (*iteri).second;
for_each(new_paths.begin(), new_paths.end(), [&] (vector<string> &path) {
path.push_back(temp);
});
if(inter_set.find(temp) == inter_set.end())
inter_set[temp] = new_paths;
else {
for_each(new_paths.begin(), new_paths.end(), [&] (vector<string> &path) {
inter_set[temp].push_back(path);
});
}
deleting.insert(temp);
isUpdated = true;
}
}
}
}
for_each(deleting.begin(), deleting.end(), [&] (const string &s) {
dict.erase(s);
});
*set_cur = inter_set;
}
return res;
}
};``````

• impressive. super fast!!

• Here is my 88ms solution use two-end BFS:

``````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 ? true : findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
}
private:
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();
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.