fork download
copy 
  1. #include <unordered_set>
  2. #include <string>
  3. #include <vector>
  4. #include <climits>
  5. #include <cstddef>
  6. #include <queue>
  7.  
  8.  
  9. namespace word_ladder {
  10.  
  11. 	[[nodiscard]] auto generate(std::string const & from,
  12. 	                            std::string const & to,
  13. 	                            std::unordered_set<std::string> const & lexicon)
  14. 	   -> std::vector<std::vector<std::string>> {
  15. 		std::vector<std::vector<std::string>> answer;
  16.  
  17. 		std::unordered_set<std::string> words;
  18. 		words.insert(lexicon.cbegin(), lexicon.cend());
  19.  
  20. 		std::queue<std::vector<std::string>> paths;
  21. 		paths.push({from});
  22.  
  23. 		std::size_t level = 1;
  24. 		std::size_t minLevel = INT_MAX;
  25.  
  26. 		std::unordered_set<std::string> visited;
  27.  
  28. 		while (!paths.empty()) {
  29. 			std::vector<std::string> path = paths.front();
  30. 			paths.pop();
  31. 			if (path.size() > level) {
  32. 				for (std::string w : visited) {
  33. 					words.erase(w);
  34. 				}
  35. 				visited.clear();
  36. 				if (path.size() > minLevel) {
  37. 					break;
  38. 				}
  39. 				else {
  40. 					level = path.size();
  41. 				}
  42. 			}
  43.  
  44. 			std::string last = path.back();
  45. 			for (std::size_t i = 0; i < last.size(); ++i) {
  46. 				std::string news = last;
  47. 				for (char c = 'a'; c <= 'z'; ++c) {
  48. 					news[i] = c;
  49. 					if (words.find(news) != words.end()) {
  50. 						std::vector<std::string> newpath = path;
  51. 						newpath.push_back(news);
  52. 						visited.insert(news);
  53. 						if (news == to) {
  54. 							minLevel = level;
  55. 							answer.push_back(newpath);
  56. 						}
  57. 						else {
  58. 							paths.push(newpath);
  59. 						}
  60. 					}
  61. 				}
  62. 			}
  63. 		}
  64. 		return answer;
  65. 	}
  66.  
  67. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/T7mLbx
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!