Leetcode 126 Solution

Solution

``````class Solution {
vector<vector<string>> res;

public:
void generate_result(const string& beginWord, const string& curr, vector<string>& path, unordered_map<string, vector<string>>& last_hops)
{
path.push_back(curr);

if (beginWord == curr)
{
vector<string> path_res = path;
reverse(path_res.begin(), path_res.end());
res.push_back(path_res);
path.pop_back();
return;
}

auto prevs = last_hops[curr];
for (auto prev : prevs)
generate_result(beginWord, prev, path, last_hops);

path.pop_back();
}

vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
unordered_map<string, vector<string>> last_hops;

queue<string> q;
q.push(beginWord);

wordList.erase(beginWord);

int step = 1;

while (q.empty() == false)
{
int s = q.size();
step++;

set<string> next;
for (int i = 0; i < s; i++)
{
auto str = q.front();
q.pop();

bool found = false;
for (int j = 0; j < str.size(); j++)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
if (ch == str[j])
continue;

auto next_str = str;
next_str[j] = ch;

if (next_str == endWord)
{
vector<string> path;
path.push_back(endWord);
generate_result(beginWord, str, path, last_hops);
found = true;
break;
}

if (wordList.find(next_str) != wordList.end())
{
if (last_hops.find(next_str) == last_hops.end())
last_hops[next_str] = vector<string>();
last_hops[next_str].push_back(str);

next.insert(next_str);
}
}

if (found)
break;
}
}

if (res.size())
break;

for (auto& str : next)
{
wordList.erase(str);
q.push(str);
}
}

return res;
}
};
``````