#include <unordered_set>
#include <string>
#include <vector>
#include <climits>
#include <cstddef>
#include <queue>


namespace word_ladder {

	[[nodiscard]] auto generate(std::string const & from,
	                            std::string const & to,
	                            std::unordered_set<std::string> const & lexicon)
	   -> std::vector<std::vector<std::string>> {
		std::vector<std::vector<std::string>> answer;

		std::unordered_set<std::string> words;
		words.insert(lexicon.cbegin(), lexicon.cend());

		std::queue<std::vector<std::string>> paths;
		paths.push({from});

		std::size_t level = 1;
		std::size_t minLevel = INT_MAX;

		std::unordered_set<std::string> visited;

		while (!paths.empty()) {
			std::vector<std::string> path = paths.front();
			paths.pop();
			if (path.size() > level) {
				for (std::string w : visited) {
					words.erase(w);
				}
				visited.clear();
				if (path.size() > minLevel) {
					break;
				}
				else {
					level = path.size();
				}
			}

			std::string last = path.back();
			for (std::size_t i = 0; i < last.size(); ++i) {
				std::string news = last;
				for (char c = 'a'; c <= 'z'; ++c) {
					news[i] = c;
					if (words.find(news) != words.end()) {
						std::vector<std::string> newpath = path;
						newpath.push_back(news);
						visited.insert(news);
						if (news == to) {
							minLevel = level;
							answer.push_back(newpath);
						}
						else {
							paths.push(newpath);
						}
					}
				}
			}
		}
		return answer;
	}

}